Statement : C. Find the Zero

This is an interactive problem.

You are given an integer $n$. There is a hidden array $a$ of length $2n$. Each integer from $1$ to $n$ appears exactly once in $a$. The rest of the elements are all $0$.

You can make the following type of query:

• Choose two integers $i$ and $j$ ($1 \le i,j \le 2n$, $i \ne j$). The judge will respond with $1$ if $a_i=a_j$, and will respond with $0$ otherwise.

Find any integer $k$ ($1 \le k \le 2n$) such that $a_k=0$ in no more than $n+1$ queries. Note that the interactor is adaptive, which means that the hidden array $a$ may change depending on your queries but will not contradict previous queries.

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($2 \le n \le 10^4$). The length of the hidden array $a$ will be $2n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^4$.

Input

2
2

0

1

3

1

0

0

Output

? 1 2

? 3 1

! 3

? 5 6

? 2 4

? 1 3

! 6

Note

In the first example test case, the hidden array $a$ is $[0,1,0,2]$:

• In the first query, $(i,j)=(1,2)$. Since $a_1=0$, $a_2=1$, $a_1 \ne a_2$, the judge responds with $0$.

• In the second query, $(i,j)=(3,1)$. Since $a_3=0$, $a_1=0$, $a_3 = a_1$, the judge responds with $1$.

• The program reports $k=3$ as an answer. Since $a_3=0$, the answer is correct.

In the second example test case, the hidden array $a$ is $[3,2,0,1,0,0]$:

• In the first query, $(i,j)=(5,6)$. Since $a_5=0$, $a_6=0$, $a_5 = a_6$, the judge responds with $1$.

• In the second query, $(i,j)=(2,4)$. Since $a_2=2$, $a_4=1$, $a_2 \ne a_4$, the judge responds with $0$.

• In the third query, $(i,j)=(1,3)$. Since $a_1=3$, $a_3=0$, $a_1 \ne a_3$, the judge responds with $0$.

• The program reports $k=6$ as an answer. Since $a_6=0$, the answer is correct.