# [Solution] Tournament Countdown solution codeforces

Tournament Countdown solution codeforces – There was a tournament consisting of 2𝑛2n contestants. The 11-st contestant competed with the 22-nd, the 33-rd competed with the 44-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.

## [Solution] Tournament Countdown solution codeforces

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 11 if 𝑎a won more matches than 𝑏b22 if 𝑏b won more matches than 𝑎a, or 00 if their number of wins was equal.

Find the winner in no more than 132𝑛+1⌈13⋅2n+1⌉ queries. Here 𝑥⌈x⌉ 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

The first line contains a single integer 𝑡t (1𝑡2141≤t≤214) — the number of test cases.

The only line of input contains a single integer 𝑛n (1𝑛171≤n≤17).

It is guaranteed that the sum of 2𝑛2n over all test cases does not exceed 217217.

## [Solution] Tournament Countdown solution codeforces

The interaction for each test case begins by reading the integer 𝑛n.

To make a query, output “? a b” (1𝑎,𝑏2𝑛1≤a,b≤2n) without quotes. Afterwards, you should read one single integer — the answer for your query. You can make at most 132𝑛+1⌈13⋅2n+1⌉ such queries in each test case.

When you are ready to give the final answer, output “! x” (1𝑥2𝑛1≤x≤2n) without quotes — the winner of the tournament. Giving this answer does not count towards the limit of queries. After solving a test case, your program should move to the next one immediately. After solving all test cases, your program should be terminated immediately.

After printing a query or the answer do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

## [Solution] Tournament Countdown solution codeforces

To hack, use the following format.

The first line contains an integer 𝑡t (1𝑡2141≤t≤214) — the number of test cases.

The first line of each test case contains a single integer 𝑛n (1𝑛171≤n≤17).

The second line of each test case contains 2𝑛2n numbers on a line — the number of wins of each participant. There should be a sequence of matches that is consistent with the number of wins.

The sum of 2𝑛2n should not exceed 217217.

Example
input

Copy
1
3

? 1 4

? 1 6

? 5 7

! 7
output

Copy
2

0

2


## [Solution] Tournament Countdown solution codeforces

The tournament in the first test case is shown below. The number of wins is [1,0,0,2,0,1,3,0][1,0,0,2,0,1,3,0].

In this example, the winner is the 77-th contestant.