Description

Bob 有一棵 $n$ 个点的无根树 $T$，树上每个点都有权值，第 $i$ 个点的权值为 $a_i$。Alice 记录了一个 $n\times n$ 的矩阵 $b$，其中 $b_{i,j}$ 表示树上 $i\to j$ 最短路径上所有点的点权的异或和。

Alice 观察这个矩阵，惊奇地发现矩阵里所有数都是正整数。

不幸的是，某一天，Bob 把他的树搞丢了。于是你得到了 Alice 记录的矩阵，并需要还原出一种可能的树 $T$ 与序列 $a$。值得注意的是，Alice 非常靠谱，因此你总是可以还原出至少一种树。

Input Format

本题有多组测试数据，第一行输入一个正整数 $T$，代表数据组数。

对于每组数据：

• 第一行输入一个正整数 $n$。
• 接下来 $n$ 行，每行 $n$ 个正整数，其中第 $i$ 行第 $j$ 个数表示 $b_{i,j}$。

Output Format

对于每组数据：

• 第一行输出 $n$ 个数，分别代表每个点的点权 $a_1,a_2,\cdots,a_n$。
• 接下来 $n-1$ 行，每行输出两个数 $u,v$，代表有一条连接 $u,v$ 的边。

2
3
1 3 7
3 2 6
7 6 4
5
8 9 10 15 1 
9 1 2 14 9 
10 2 3 13 10 
15 14 13 7 6 
1 9 10 6 8 

1 2 4 
1 2
2 3
8 1 3 7 8 
1 2
1 4
2 3
2 5

1
2
10000000000 29999508480
29999508480 20000000000

10000000000 20000000000
1 2

Hint

对于所有数据，保证：

• $1\le T\le 10$
• $1\le n\le 500$
• $1\le b_{i,j}<2^{60}$

本题采用捆绑测试，各子任务描述如下：

• Subtask 1（5 pts）：$n=2$。
• Subtask 2（10 pts）：$n=3$。
• Subtask 3（10 pts）：$n=4$。
• Subtask 4（15 pts）：$n\le 8$。
• Subtask 5（25 pts）：$b_{i,i}$ 互不相同。
• Subtask 6（35 pts）：无特殊限制。