题目描述

Yuki 有一棵包含 $2^n$ 个结点的树，结点的编号为 $0$ 至 $2^n - 1$，第 $i$ 条边连接结点 $u_i$ 与结点 $v_i$。

设 $\operatorname{lca}_{r}(u, v)$ 表示，以结点 $r$ 为根时，结点 $u$ 与结点 $v$ 的最近公共祖先。你需要帮助 Yuki 求出：

$$\bigoplus_{0 \le u < v < 2^n} \operatorname{lca}_{u \oplus v}(u, v)$$

其中 $\oplus$ 表示按位异或运算。

输入格式

本题包含多组测试数据。

第一行包含一个正整数 $t$ $(1 \le t \le 10^4)$，表示测试数据组数。

对于每组测试数据：

• 第一行包含一个正整数 $n$ $(1 \le n \le 21)$。
• 接下来 $2^n - 1$ 行，第 $i$ 行包含两个正整数 $u_i, v_i$ $(0 \le u_i, v_i < 2^n,\ u_i \ne v_i)$。

保证输入数据形成一棵树，保证所有测试数据中 $2^n$ 的总和不超过 $2^{21}$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示答案。

4
1
0 1
2
0 1
1 2
2 3
3
0 1
0 2
0 3
0 4
0 5
0 6
0 7
3
4 5
2 6
3 7
0 2
1 5
2 7
6 4

1
2
0
4

提示

对于第 $1$ 组测试数据：

• 以结点 $1$ 为根时，结点 $0$ 与结点 $1$ 的最近公共祖先为结点 $1$，因此答案为 $\operatorname{lca}_1(0, 1) = 1$。

对于第 $2$ 组测试数据：

• 我们计算所有点对 $(u, v)$ 的 $\operatorname{lca}_{u \oplus v}(u, v)$：
  • $(0, 1)$：$0 \oplus 1 = 1$，$\operatorname{lca}_1(0, 1) = 1$。
  • $(0, 2)$：$0 \oplus 2 = 2$，$\operatorname{lca}_2(0, 2) = 2$。
  • $(0, 3)$：$0 \oplus 3 = 3$，$\operatorname{lca}_3(0, 3) = 3$。
  • $(1, 2)$：$1 \oplus 2 = 3$，$\operatorname{lca}_3(1, 2) = 2$。
  • $(1, 3)$：$1 \oplus 3 = 2$，$\operatorname{lca}_2(1, 3) = 2$。
  • $(2, 3)$：$2 \oplus 3 = 1$，$\operatorname{lca}_1(2, 3) = 2$。
• 异或和为 $1 \oplus 2 \oplus 3 \oplus 2 \oplus 2 \oplus 2 = 2$。