P12531 [XJTUPC 2025] Beat Verdict: Precision Strike

**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.

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.

See also interactive format.

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.