CF1713D.Tournament Countdown

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.

这是一个交互式问题。

曾经举办过一场有 $2^n$ 名参赛者的比赛。第 $1$ 名参赛者与第 $2$ 名参赛者对决，第 $3$ 名参赛者与第 $4$ 名参赛者对决，以此类推。之后，第一场对决的胜者与第二场对决的胜者再进行对决，依此类推。当场上仅剩一名参赛者时，比赛结束，该参赛者即被宣布为整场比赛的冠军。这种赛制被称为单败淘汰制。

你并不知道比赛结果，但你想找出最终的冠军。在一次查询中，你选择两个整数 $a$ 和 $b$，分别代表两名参赛者的编号。评测系统将返回：若 $a$ 获胜的场数多于 $b$，则返回 $1$；若 $b$ 获胜的场数多于 $a$，则返回 $2$；若二者获胜场数相等，则返回 $0$。

请在不超过 $\left \lceil \frac{1}{3} \cdot 2^{n + 1} \right \rceil$ 次查询内找出冠军。其中 $\lceil x \rceil$ 表示将 $x$ 向上取整后的整数值。

注意：这场比赛早已结束，因此所有比赛结果是固定的，不随你的查询而改变。

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}$.

第一行包含一个整数 $t$（$1 \leq t \leq 2^{14}$）—— 表示测试用例的数量。

输入的唯一一行包含一个整数 $n$（$1 \leq n \leq 17$）。

保证所有测试用例中 $2^n$ 的总和不超过 $2^{17}$。

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.

第一个测试用例中的锦标赛如下图所示。各参赛者的获胜次数为 $[1,0,0,2,0,1,3,0]$。

本例中，冠军是第 $7$ 号参赛者。