I. Lulu And The Magical Array
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

"You'll see more with your eyes closed" — Lulu

On Lulu's birthday, Pix comes up with a great present, a magical integer array $$$A$$$ of length $$$n$$$. The number of this array cannot be seen by eyes, but Lulu can cast a magical query asking for the bitwise XOR of 2 distinct elements of the array. More formally, Lulu can ask for the value of $$$A[i] \oplus A[j] (i\neq j)$$$ where $$$\oplus$$$ denotes the bitwise XOR operator. (You can find more details about the bitwise XOR operator in the notes.)

With her eyes closed, Lulu is certain that she can tell the minimum of the bitwise XOR between any 2 distinct elements of the array $$$A$$$ by casting no more than $$$n$$$ magical queries.

More formally, Lulu needs to find $$$min_{1 \leq i,j \leq n, i\ne j} A[i] \oplus A[j]$$$

Please help Lulu find this number!

Input

Each test contains multiple test cases. The first line contains a single integer $$$t(1\leq t \leq 10000)$$$ — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n(2 \leq n \leq 2\cdot 10^5)$$$

It's guaranteed that $$$0 \leq A[i] \lt 2^{30}$$$ $$$(1 \le i \le n)$$$ and the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Interaction

You can ask no more than $$$n$$$ magical queries by outputting a single line of the form

$$$\texttt{?}~i~j$$$ $$$(1 \leq i,j \leq n, i \neq j)$$$.

The interactor will respond with a single integer, the value of $$$A[i] \oplus A[j]$$$ or -1 if you ask more than $$$n$$$ queries or make an invalid query.

Output

When you are ready to report the answer, output a single line of the form

$$$\texttt{!}~x$$$

where $$$x=$$$ $$$min_{1 \leq i,j \leq n, i\ne j} A[i] \oplus A[j]$$$.

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

  • fflush(stdout) or cout.flush() in C/C++;
  • System.out.flush() in Java and Kotlin;
  • sys.stdout.flush() in Python;
Examples
Input
1
5
 
13
 
7
 
3
 
11
 
9
Output
 
 
? 1 2
 
? 2 4
 
? 1 3
 
? 5 2
 
? 3 4
 
! 3
Note

Explanation of an example

The array in the example is $$$[12,1,15,6,10]$$$.

For the first two inputs, the number of test cases(1) and $$$n$$$ for the first test case are given.

Then, Lulu makes queries for $$$5$$$ times in this order.

  1. $$$?$$$ $$$1$$$ $$$2$$$ and the interactor responds with $$$12 \oplus 1 = 13$$$.
  2. $$$?$$$ $$$2$$$ $$$4$$$ and the interactor responds with $$$1 \oplus 6 = 7$$$.
  3. $$$?$$$ $$$1$$$ $$$3$$$ and the interactor responds with $$$12 \oplus 15 = 3$$$.
  4. $$$?$$$ $$$5$$$ $$$2$$$ and the interactor responds with $$$10 \oplus 1 = 11$$$.
  5. $$$?$$$ $$$3$$$ $$$4$$$ and the interactor responds with $$$15 \oplus 6 = 9$$$.

After Lulu is certain that the answer is $$$3$$$, she reports the answer by outputting $$$!$$$ $$$3$$$.

Bitwise XOR

A bitwise XOR is a binary operation that takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is $$$1$$$ if only one of the bits is $$$1$$$, but will be $$$0$$$ if both are $$$0$$$ or both are $$$1$$$. In this, we perform the comparison of two bits, being $$$1$$$ if the two bits are different, and $$$0$$$ if they are the same. For example:

         $$$0101$$$ (decimal $$$5$$$)

XOR $$$0011$$$ (decimal $$$3$$$)

$$$=$$$      $$$0110$$$ (decimal $$$6$$$)