当前没有测试数据。

3.石子游戏

题目描述

小明与小红正在一棵满二叉树（叶结点深度均相同，非叶结点均有两个儿子）上玩游戏。这棵满二叉树的高度为$k$，第$i$层有$2^{i-1}$个结点，因此这棵树共有$2^{k}-1$个结点。

树上的结点从$1 \sim 2^{k}-1$进行编号，$1$号点为根结点，并且对于非叶结点$i$，它的两个儿子分别为$2i$与$2i+1$。游戏开始前每个结点上都放有一定数量的石子，$i$号点上的石子数量为$a_{i}$。游戏开始后，小明和小红轮流行动，小明先手。当前行动的人需要先选择一个树中的结点$u$并且要满足$u$上还有石子。接下来，若$u$是个叶子结点，则他需要彻底移除至少一个$u$上的石子；若$u$是个非叶结点，则他需要移除至少一个$u$上的石子，并将这些石子移动到$u$的其中一个儿子上（一次操作不能分开移动，必须移动至同一个儿子）。无法操作者即为负。

假设小明和小红都足够聪明，以最优策略玩这个游戏，请你求出小明有多少种第一步的操作方式能够让小明获胜。

输入格式

第一行一个整数$T$表示数据组数。

每组数据第一行一个整数$k$表示树高。

接下来$k$行，第$i$行$2^{i-1}$个非负整数表示初始时第$i$层结点上的石子数$a_{i}$（按标号顺序给出）。

输出格式

对于每组数据输出一行一个整数表示答案。

数据范围与提示

• 对于$30\%$的数据，$T=1$，$k \leq 2$，$a_{i} \leq 5$；
• 对于$60\%$的数据，$T < 5$，$k \leq 8$，$a_{i} \leq 10^{5}$；
• 对于$100\%$的数据，$T < 10$，$1 \leq k \leq 16$，$0 \leq a_{i} \leq 10^{9}$。

样例

3
1
1
2
1
0 0
3
1
2 2
4 4 4 4

1
0
6