This is an interactive problem.

You stand in a damp, moldy place of gloomy rain, unheeded by anyone, singing a song with no audience, waiting for that person to appear.

At last, she walks in from around the corner. This time, she does not "linger for a moment before leaving", but instead invites you to face the ending together...

At this moment, a combination lock $$$a$$$ of length $$$n$$$ emerges in the collapsing sky. Each digit $$$a_i$$$ is in the range $$$[1,n]$$$. It is guaranteed that initially, not all $$$a_i$$$ are equal. You may now perform the following operation:

• Choose an index $$$pos$$$ ($$$1 \leq pos \leq n$$$). You may turn the $$$pos$$$-th dial forward by $$$1$$$ step (i.e., $$$a_{pos} \rightarrow (a_{pos} \bmod n) + 1$$$). Then, you will be informed whether there exists any number in the array equal to $$$a_{pos}$$$ (excluding $$$a_{pos}$$$ itself).

The lock is unlocked when all digits are equal (they do not necessarily have to become $$$1$$$).

The end of the world is fast approaching. You must unlock this combination lock within $$$\lceil\frac{3n(n+1)}{2}\rceil$$$ operations to prevent the world's destruction.

This problem contains multiple test cases. First, your program must read an integer $$$T$$$ ($$$1 \leq T \leq 100$$$) from standard input.

In a single test case:

First, your program reads an integer $$$n$$$ ($$$3 \leq n \leq 100$$$) from standard input.

Then, you may perform an operation using the format ? pos. The interactor will then return 0 or 1, indicating whether there is any number in the array equal to $$$a_{pos}$$$ ($$$0$$$ means no, $$$1$$$ means yes). If you performed an illegal operation or used more than $$$\lceil\frac{3n(n+1)}{2}\rceil$$$ operations, you will read $$$-1$$$, in which case you should terminate your program immediately to avoid unexpected results.

When you believe you have unlocked the combination lock, you must output ! and proceed directly to the next test case. It does not count towards operations. If in any test case you fail to unlock the combination lock, your solution will be judged as Wrong Answer.

It is guaranteed that $$$\sum n \leq 10^3$$$.

After printing a query, do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded or Time 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.