Buffett is very fond of perfect trees. One day, he decided to plant a tree himself using a mysterious seed given to him by Mao Kai.

This seed has very vigorous vitality. After planting the seed, if we denote the seed planted on the first day as the initial leaf node, then starting from the second day, every leaf node that sprouted the previous day will grow two new leaf nodes. In other words, if this tree has grown for $k$ days, it is a full binary tree with $2^k - 1$ nodes.

Due to its rapid growth rate, Buffett was quickly able to obtain a full binary tree with many nodes, and he considered the full binary tree to be very perfect.

Mao Kai also knew that Buffett was very fond of trees, so he brought him a gift: another tree grown from the same kind of mysterious seed (the sizes may not be the same). However, Buffett already had one such tree, and it was inconvenient to store two trees, so he connected the two trees with an extra edge, forming a single tree.

Obviously, such a tree is no longer a perfect full binary tree, so Buffett soon threw it into a corner.

After a long, long time, Buffett remembered this new tree formed by connecting two full binary trees, and he wanted to split this tree back into two full binary trees, but he had already forgotten which edge was the one he added extra.

Hopefully, you, being clever, can help Buffett solve this problem.

Formally, given a tree, you need to delete one of its edges such that the two resulting trees are both full binary trees. It is guaranteed that at least one such solution exists.

*A full binary tree is defined as a binary tree where all leaf nodes have the same depth, and all non-leaf nodes have exactly 2 child nodes.

Input

The input contains multiple test cases. The first line contains a single integer $T$ ($1 \le T \le 10^5$), representing the number of test cases. The following is a description of the test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2^{17} - 2$), representing the number of nodes in the tree Buffett has.

The next $n - 1$ lines each contain two space-separated integers $u_i, v_i$ ($1 \le u_i, v_i \le n$), representing an edge $(u_i, v_i)$ in the tree. The input guarantees that the given edges form a tree.

Additionally, it is guaranteed that $\sum n \le 10^6$.

Output

For each test case, output a single integer $i$ on a line, representing that if the $i$-th edge $(u_i, v_i)$ from the given edges is deleted, the two resulting trees are both full binary trees. It is guaranteed that such a solution exists. If there are multiple possible solutions, output any one of them.

Examples

Input 1

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

Output 1

1
4
7

Note

The tree in the second example is shown in the figure above. It can be found that only deleting the edge (2, 4) is valid.

The tree in the third example is shown in the figure above. It can be found that deleting the edge (1, 2), (1, 3), or (1, 8) are all valid; you can output any one of them.