题目描述

这是一道交互题。

给你一个整数 $n$，存在一个长度为 $2n$ 的隐藏数组 $a$，数字 $1$ 到 $n$ 每个数恰好在数组中出现一次，数组里剩下的元素全都是 $0$。

你可以进行这样的询问操作：选择两个整数 $i$ 和 $j$（$1 \le i,j \le 2n$，且 $i \neq j$），裁判会给出回应：如果 $a_i = a_j$，回应 $1$；如果 $a_i \neq a_j$，回应 $0$。

请你在不超过 $n+1$ 次询问内，找到任意一个满足 $a_k = 0$ 的整数 $k$（$1 \le k \le 2n$）。

注意，交互器是自适应的，也就是说隐藏数组 $a$ 可能会根据你的询问发生变化，但不会和之前的询问结果矛盾。

输入格式

输入包含多组测试用例，第一行是测试用例的数量 $t$（$1 \le t \le 10^3$）。

接下来每组测试用例占一行，每行有一个整数 $n$（$2 \le n \le 10^4$），隐藏数组 $a$ 的长度为 $2n$。

保证所有测试用例的 $n$ 之和不超过 $10^4$。

交互方式

发起询问时，需要按如下格式输出一行： ? $i$ $j$

裁判会给出对应的回应：

• 若 $a_i = a_j$，返回 $1$；
• 若 $a_i \neq a_j$，返回 $0$；
• 若你的询问无效，或者询问次数超过了 $n+1$ 次，返回 $-1$。

得出答案后，需要按如下格式输出一行： ! $k$

输出答案后，继续处理下一组测试用例即可，如果是最后一组，直接结束程序。

注意，输出答案的操作不计入 $n+1$ 次的询问限制。

交互器是自适应的，意味着隐藏数组 $a$ 可能会根据你的询问改变，但不会和之前的询问结果冲突。

每次输出询问内容后，一定要输出换行并刷新输出缓冲区，否则会被判超时。如果在交互过程中读到了 $-1$ 而非有效数据，你的程序必须立即退出，否则会被判错误，继续读取会导致结果不可控。

输入输出样例

2
2
0
1
3
1
0
0

? 1 2
? 3 1
! 3
? 5 6
? 2 4
? 1 3
! 6

样例说明

第一组测试用例中，隐藏数组 $a = [0,1,0,2]$：

1. 第一次询问选择 $(i,j)=(1,2)$，因为 $a_1=0$，$a_2=1$，二者不相等，裁判回应 $0$；
2. 第二次询问选择 $(i,j)=(3,1)$，因为 $a_3=0$，$a_1=0$，二者相等，裁判回应 $1$；
3. 程序输出答案 $k=3$，满足 $a_3=0$，答案正确。

第二组测试用例中，隐藏数组 $a = [3,2,0,1,0,0]$：

1. 第一次询问选择 $(i,j)=(5,6)$，因为 $a_5=0$，$a_6=0$，二者相等，裁判回应 $1$；
2. 第二次询问选择 $(i,j)=(2,4)$，因为 $a_2=2$，$a_4=1$，二者不相等，裁判回应 $0$；
3. 第三次询问选择 $(i,j)=(1,3)$，因为 $a_1=3$，$a_3=0$，二者不相等，裁判回应 $0$；
4. 程序输出答案 $k=6$，满足 $a_6=0$，答案正确。

来源

Codeforces Contest 2209 Problem C https://codeforces.com/contest/2209/problem/C