Description

$Alice$ 与 $Bob$ 正在一棵满二叉树（叶结点深度均相同，非叶结点均有两个儿子）上玩游戏。这棵满二叉树的高度 $k$, 为第 $i$ 层有 $2 ^ {ｉ-１}$ 个结点，因此这棵树共有 $2^k - 1$ 个结点，树上的结点从 $1 \sim 2^k - 1$进行编号， $1$ 号点为根结点，并且对于非叶结点 $i$，它的两个儿子分别为 $2i$ 与 $2i + 1$.

游戏开始前每个结点上都放有一定数量的石子， $i$ 号点上的石子数量为 $a_i$.

游戏开始后， $Alice$ 和 $Bob$ 轮流行动， $Alice$ 先手。当前行动的人需要先选择一个树中的结点 $u$ 并且要满足 $u$ 上还有石子。接下来，若 $u$ 是个叶子结点,则他需要彻底移除至少一个 $u$ 上的石子；若 $u$ 是个非叶结点，则他需要移除至少一个 $u$ 上的石子，并将这些石子移动到 $u$ 的其中一个儿子上（一次操作不能分开移动，必须移动至同一个儿子)。无法操作者即为负。

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

Input Format

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

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

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

Output Format

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

Sample

样例输入

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

样例输出

1
0
6

Hint

$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$