Description

Bob has an unrooted tree $T$ with $n$ vertices. Each vertex has a weight, with the weight of vertex $i$ being $a_i$. Alice has recorded an $n \times n$ matrix $b$, where $b_{i,j}$ is the XOR sum of the weights of all vertices on the shortest path from vertex $i$ to vertex $j$.

Alice observed this matrix and, to her surprise, found that all its elements are positive integers.

Unfortunately, one day, Bob lost his tree. Now, you are given Alice's matrix $b$, and your task is to reconstruct a possible tree $T$ and the sequence of weights $a$. It is worth noting that Alice is very reliable, so it is guaranteed that at least one such tree can always be reconstructed.

Input Format

The input consists of multiple test cases. The first line contains a single positive integer $T$, representing the number of test cases.

For each test case:

• The first line contains a positive integer $n$.
• The next $n$ lines describe the matrix $b$. The $j$-th integer on the $i$-th of these lines is $b_{i,j}$.

Output Format

For each test case:

• In the first line, output $n$ integers, representing the vertex weights $a_1, a_2, \ldots, a_n$.
• Then, output $n-1$ lines. Each line should contain two integers $u,v$, representing an edge between vertex $u$ and vertex $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

For all test data, it is guaranteed that:

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

This problem uses bundled tests. The subtasks are described as follows:

• 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): The values $b_{i,i}$ are all distinct.
• Subtask 6 (35 pts): No additional constraints.