[思维]Tournament Countdown Codeforces1713D

This is an interactive problem.

There was a tournament consisting of 2n2n 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.

You don't know the results, but you want to find the winner of the tournament. In one query, you select two integers aa and bb, which are the indices of two contestants. The jury will return 11 if aa won more matches than bb, 22 if bb won more matches than aa, or 00 if their number of wins was equal.

Find the winner in no more than ⌈13⋅2n+1⌉⌈13⋅2n+1⌉ queries. Here ⌈x⌉⌈x⌉ denotes the value of xx 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 tt (1≤t≤2141≤t≤214) — the number of test cases.

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

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

Interaction

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

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

If you receive the integer −1−1 instead of an answer or a valid value of nn, it means your program has made an invalid query, has exceed the limit of queries, or has given incorrect answer on the previous test case. Your program must terminate immediately to receive a Wrong Answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.

When you are ready to give the final answer, output "! x" (1≤x≤2n1≤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.

Hacks

To hack, use the following format.

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

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

The second line of each test case contains 2n2n 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 2n2n should not exceed 217217.

Example

input

1
3

2

0

2

output

? 1 4

? 1 6

? 5 7

! 7

题意： 有2^n个选手参与锦标赛，最下层按照1~2^n排列，具体的输赢已经确定，现在你可以询问a和b，程序将告诉你谁胜利次数多，如何在2^(n+1)/3次询问内找到最终的胜者。

分析： 2^(n+1)/3也就是(2/3)*2^n，一共会进行2^n-1次比赛，所以需要减少1/3的询问数，也就是对于这样的三场比赛只用两次询问得到结果：

而具体实现也很简单，先询问1和3，然后假如是1获胜的次数多，那就再问1和4，而如果1和3胜利次数相同，那就可以问2和4，通过这样的方式就能知道这颗子树的最终胜者。所以可以在这个满二叉树上递归处理得到答案。

具体代码如下：

#include 
#include 
#include 
#include 
#include 
using namespace std;
 
int tr[1<<20];
 
signed main()
{
	int T;
	cin >> T;
	while(T--){
		int n;
		scanf("%d", &n);
		int num = 1<
		for(int i = 1; i <= num; i++)
			tr[i+num-1] = i; 
		int now = n+1, res;
		while(now > 1){
			if(now == 2){
				printf("? %d %d\n", tr[2], tr[3]);
				fflush(stdout);
				scanf("%d", &res);
				if(res == 1) tr[1] = tr[2];
				else tr[1] = tr[3];
				break;
			} 
			for(int i = 1<<(now-2-1); i <= (1<<(now-2))-1; i++){
				int t1 = tr[i<<2], t2 = tr[(i<<1|1)<<1]; 
				printf("? %d %d\n", tr[i<<2], tr[(i<<1|1)<<1]);
				fflush(stdout);
				scanf("%d", &res);
				if(res == 0){
					printf("? %d %d\n", tr[i<<2|1], tr[(i<<1|1)<<1|1]);
					fflush(stdout);
					scanf("%d", &res);
					if(res == 1) tr[i] = tr[i<<2|1];
					else tr[i] = tr[(i<<1|1)<<1|1]; 
				}
				else if(res == 1){
					printf("? %d %d\n", tr[i<<2], tr[(i<<1|1)<<1|1]);
					fflush(stdout);
					scanf("%d", &res);
					if(res == 1) tr[i] = tr[i<<2];
					else tr[i] = tr[(i<<1|1)<<1|1]; 
				}
				else{
					printf("? %d %d\n", tr[i<<2|1], tr[(i<<1|1)<<1]);
					fflush(stdout);
					scanf("%d", &res);
					if(res == 1) tr[i] = tr[i<<2|1];
					else tr[i] = tr[(i<<1|1)<<1]; 
				}
			}
			now -= 2;
		}
		printf("! %d\n", tr[1]); 
		fflush(stdout);
	}
	return 0;
}