Description

This is an interactive problem.

You are playing a music game. In expert mode, you need to accurately calibrate the timing parameter for hitting notes, which is a mysterious $\textbf{integer}$ $x$ within the range $[1,n]$.

To determine this parameter, you can perform at most $4$ calibration tests. In each test, you choose an $\textbf{integer}$ test value $y$ ($1 \le y \le n$), and the system will inform you whether $y > x$ is true or not. Ultimately, you need to provide an $\textbf{integer}$ estimated parameter value $x'$ ($1 \le x' \le n$), such that $x' \in \left[0.5x, 2x\right]$.

Note: The final estimated value $x'$ does not count towards the aforementioned maximum of $4$ tests.

Input Format

The input contains multiple test cases. The first line of the data contains an integer $t$ ($1\le t\le 500$) indicating the number of test cases. The interaction process for each test case is described below.

In each test case, the first line of input contains a positive integer $n$ ($1\le n \le 5 \times 10^9$), representing the possible range of the parameter.

If you want to perform a calibration test, output $\tt{?\ y}$ ($1 \le y \le n$). Then you will read the response to that test, which will be an integer $a$ ($a \in \{0, 1\}$), where $\tt{1}$ indicates that $y>x$ is true, and $\tt{0}$ indicates that $y>x$ is false.

If you want to submit the calibration parameter $x'$, output $\tt{!\ x'}$ ($1 \le x' \le n$). You will then immediately end the interaction for this test case and prepare for the interaction of the next test case. This interaction does not count towards the maximum of $4$ tests.

Note that at the end of each round of output in your program (i.e., after each output of $\tt{?\ y}$ or $\tt{!\ x'}$), $\textbf{you need to output a newline and flush the output buffer}$; otherwise, you will receive $\tt{Time\ Limit\ Exceeded}$.

You can use:

• C's $\tt{fflush(stdout)}$;
• C++'s $\tt{cout.flush()}$;
• Java's $\tt{System.out.flush()}$;
• Python's $\tt{stdout.flush()}$;

to flush the output buffer.

Please note: The interactive library is adaptive, meaning that the positive integer $x$ ($1 \le x \le n$) $\textbf{may change with your inputs}$ in each test case, but it will always satisfy all previously made inquiries.

If the answer you output at the end is correct, you will receive $\tt{Accepted}$;

If your inquiries do not conform to the problem's range requirements, or if the final answer you output is incorrect, you will receive $\tt{Wrong Answer}$;

Additionally, other evaluation results will still be returned during the evaluation process based on normal circumstances.

Output Format

See also interactive format.

2
1

8

1

1

0

0

! 1

? 6

? 4

? 2

? 3

! 3

Hint

In the first test case, it can be uniquely determined that $x = 1$, so we directly submit $x' = 1$.

In the second test case, the hidden parameter $x = 3$, and the interaction process is as follows:

• Test $y=6$, the response is that $y>x$ is true;
• Test $y=4$, the response is that $y>x$ is true;
• Test $y=2$, the response is that $y>x$ is false;
• Test $y=3$, the response is that $y>x$ is false;
• Submit $x' = 3$.

Please note that this example only serves to demonstrate the interaction format. It is not guaranteed that the queries provided are optimal or uniquely determine the answer.