Background

意気込むことはないけれど　/　Although I'm not always motivated,

生きていけるよ　君をさがして　/　I can keep living while searching for you.

Description

Given a positive integer $h$, let $n=2^h-1$.

You are given the values of $f_{u,k}$ for every positive integer $u \le n$ and every positive integer $k \le 2h-2$. You need to construct a pair $(r, w)$ such that $1 \le r \le n$ and $0 \le w < 2^{30}$, for which there exists a full binary tree $T$ of height $h$ satisfying:

• The labels of all nodes in the full binary tree $T$ form a permutation of $1 \sim n$, and each node has a weight;
• The root of the full binary tree $T$ is node $r$;
• The weight of each node in the full binary tree $T$ is a non-negative integer less than $2^{30}$, and the weight of the root is $w$;
• For every positive integer $u \le n$ and every positive integer $k \le 2h-2$, the XOR sum of the weights of all nodes $v$ such that $\operatorname{dis}(u, v) = k$ is equal to $f_{u,k}$. Specifically, if no such node $v$ exists, then $f_{u,k} = 0$.

Here, $\operatorname{dis}(u, v)$ is the number of edges on the simple path between node $u$ and node $v$. Specifically, $\operatorname{dis}(u, u) = 0$.

It is guaranteed that at least one pair $(r, w)$ satisfying the conditions exists.

Input

The first line contains an integer $T$, representing the number of test cases.

The input for each test case follows:

• The first line contains a positive integer $h$.
• The next $n$ lines each contain $2h-2$ integers, where the $k$-th integer represents the value of $f_{u,k}$.

Output

For each test case, output two integers on a single line, representing the values of $r$ and $w$ in your constructed pair $(r, w)$.

• If your constructed pair $(r, w)$ satisfies the conditions, you receive 100% of the points for that test case.
• Otherwise, if your pair $(r, w)$ does not satisfy the conditions, but there exists a valid pair $(r', w')$ such that $r' = r$, you receive 50% of the points for that test case.
• Otherwise, if your pair $(r, w)$ does not satisfy the conditions, but there exists a valid pair $(r', w')$ such that $w' = w$, you receive 50% of the points for that test case.
• Otherwise, you receive 0 points for that test case.

Examples

Input 1

2
2
1 0
2 0
1 2
4
75 0 89 1 0 56
0 52 19 84 1 0
0 27 19 108 1 0
0 89 1 0 56 0
85 19 108 1 0 0
75 0 89 1 0 56
1 1 56 0 0 0
0 88 19 84 1 0
0 79 19 108 1 0
74 0 88 1 0 56
0 88 1 0 56 0
109 19 84 1 0 0
19 56 1 0 0 0
74 0 88 1 0 56
18 1 0 56 0 0

Output 1

2 1
7 19

Note 1

For the first test case:

When the constructed pair is $(r, w) = (2, 1)$, there exists a binary tree as shown in the figure that satisfies the conditions, where the weights of nodes $1, 2, 3$ are $2, 1, 0$ respectively.

If you output 2 2, you receive 50% of the points for this test case because, although $(r, w) = (2, 2)$ does not satisfy the conditions, there exists a valid pair $(r', w') = (2, 1)$ such that $r' = r = 2$.

If you output 1 1, you also receive 50% of the points.

However, if you output 1 2, you will not receive any points for this test case.

Constraints

Let $\sum n$ denote the sum of $n$ over a single test case.

For all test cases, $1 \le T \le 1000$, $2 \le h \le 16$, $\sum n \le 2^{16}$, $0 \le f_{u,k} < 2^{30}$. It is guaranteed that at least one valid pair $(r, w)$ exists.

This problem uses bundled testing.

• Subtask 1 (20 points): $h = 2$.
• Subtask 2 (20 points): Satisfies the special property.
• Subtask 3 (60 points): No special restrictions.

Special property: There exists a pair $(r, w)$ with $1 \le r \le n$ and $0 \le w < 2^{30}$ such that there exists a valid full binary tree where all nodes have weight $w$.