题目描述
小明与小红正在一棵满二叉树(叶结点深度均相同，非叶结点均有两个儿子)上玩游戏。这棵满二叉树的高度为 $k$，第 $i$ 层有 $2^{i-1}$ 个结点，因此这棵树共有 $n$ 个结点。
树上的结点从 $1 \sim 2^k-1$ 进行编号，$1$ 号点为根结点，并且对于非叶结点 ，它的两个儿子分别为 $2i$ 与 $2i+1$. 游戏开始前每个结点上都放有一定数量的石子，$i$ 号点上的石子数量为 $a_i$.游戏开始后，小明和小红轮流行动，小明先手。当前行动的人需要先选择一个树中的结点 $u$ 并且要满足 $u$ 上还有石子。接下来，若 $u$ 是个叶子结点，则他需要彻底移除至少一个 $u$ 上的石子；若 $u$ 是个非叶结点，则他需要移除至少一个 $u$ 上的石子，并将这些石子移动到 的其中一个儿子上(一次操作不能分开移动，必须移动至同一个儿子)。无法操作者即为负。
假设 小明和小红都足够聪明，以最优策略玩这个游戏，请你求出 小明有多少种第一步的操作方式能够让 小明获胜。
输入
第一行一个整数 $T$ 表示数据组数。
每组数据第一行一个整数 $k$ 表示树高。
接下来 $k$ 行，第 $i$ 行 $2^{i-1}$ 个非负整数表示初始时第 $i$ 层结点上的石子数 $a_i$(按标号顺序给出)。
输出
样例输入输出
输入#1
复制
3
1
1
2
1
0 0
3
1
2 2
4 4 4 4
提示
对于 $30\%$ 的数据，$T = 1$，$k \leq 2$，$a_i \leq 5$。
对于 $60\%$ 的数据，$T \leq 5$，$k \leq 8$，$a_i \leq 10^5$。
对于 $100\%$ 的数据，$T \leq 10$，$1\leq k \leq 16$，$0\leq a_i \leq 10^6$。