F. Beat Verdict: Precision Strike
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 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 integer test value $$$y$$$ ($$$1 \le y \le n$$$), and the system will inform you whether $$$y \gt x$$$ is true or not. Ultimately, you need to provide an 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

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.

Interaction

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 ? 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 1 indicates that $$$y \gt x$$$ is true, and 0 indicates that $$$y \gt x$$$ is false.

If you want to submit the calibration parameter $$$x'$$$, output ! 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 ? y or ! x'), you need to output a newline and flush the output buffer; otherwise, you will receive Idleness Limit Exceeded.

You can use:

  • C's fflush(stdout);
  • C++'s cout.flush();
  • Java's System.out.flush();
  • Python's 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$$$) 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 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 Wrong Answer;

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

Example
Input
2
1

8

1

1

0

0
Output


! 1

? 6

? 4

? 2

? 3

! 3
Note

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:

  1. Test $$$y=6$$$, the response is that $$$y \gt x$$$ is true;
  2. Test $$$y=4$$$, the response is that $$$y \gt x$$$ is true;
  3. Test $$$y=2$$$, the response is that $$$y \gt x$$$ is false;
  4. Test $$$y=3$$$, the response is that $$$y \gt x$$$ is false;
  5. 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.