Description:
This is an interactive problem.
There was a tournament consisting of $$$2^n$$$ contestants. The $$$1$$$-st contestant competed with the $$$2$$$-nd, the $$$3$$$-rd competed with the $$$4$$$-th, and so on. After that, the winner of the first match competed with the winner of second match, etc. The tournament ended when there was only one contestant left, who was declared the winner of the tournament. Such a tournament scheme is known as the single-elimination tournament.
You don't know the results, but you want to find the winner of the tournament. In one query, you select two integers $$$a$$$ and $$$b$$$, which are the indices of two contestants. The jury will return $$$1$$$ if $$$a$$$ won more matches than $$$b$$$, $$$2$$$ if $$$b$$$ won more matches than $$$a$$$, or $$$0$$$ if their number of wins was equal.
Find the winner in no more than $$$\left \lceil \frac{1}{3} \cdot 2^{n + 1} \right \rceil$$$ queries. Here $$$\lceil x \rceil$$$ denotes the value of $$$x$$$ rounded up to the nearest integer.
Note that the tournament is long over, meaning that the results are fixed and do not depend on your queries.
Input Format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2^{14}$$$) — the number of test cases.
The only line of input contains a single integer $$$n$$$ ($$$1 \leq n \leq 17$$$).
It is guaranteed that the sum of $$$2^n$$$ over all test cases does not exceed $$$2^{17}$$$.
Output Format:
None
Note:
The tournament in the first test case is shown below. The number of wins is $$$[1,0,0,2,0,1,3,0]$$$.
In this example, the winner is the $$$7$$$-th contestant.