Description

This problem is different from B2. You had better read both statements.

This is an interactive problem.

Hint: We provide a formalized description of this problem at the end of the statement.

Madoka and Homura are playing a game.

Madoka has thought of a non-negative integer $m$, and Homura need to determine its value. It is guaranteed that $\textcolor{red}{0}\le m\le 10^{17}$. Also, Madoka doesn't cheat, that is, Madoka wouldn't change the value of $m$ during the whole game.

Homura can ask Madoka: for a positive integer $x$, what is the value of $m\bmod x$. Homura aims to determine the value of $m$ with the number of queries as small as possible. (In order to get full points, you need to solve this problem within $2$ queries.)

The game will be played for $T$ rounds. However, Homura is poor at math. Thus, she turns to you.

Formally, there exists a hidden non-negative integer $m\in [\textcolor{red}{0},10^{17}]$. In each query, a positive integer $x$ is given, and it returns $m \bmod x$.

Find $m$ with the least number of queries. There are $T$ test cases.

The value of $m$ is read from input file and does not change according to queries. That is, the interactor is non-adaptive.

Implementation Details

Input a positive integer $T$ first, which stands for the number of the rounds.

For each test case:

• Output a single line containing $\texttt{? }x$ to make a query. Then, an integer indicating $m\bmod x$ is available.

  $x$ is a positive integer should be guaranteed, and $x$ must fall in $\textcolor{red} {[1,4\times 10^8]}$.

  If $x=-1$ instead of the answer, it means that the query limit is excceeded, or the query is invalid. The solution should quit immediately.

• Output a single line containing $\texttt{! }m$ to respond to the guess.

After outputing the queries, do not forget to output a newline character and flush the output buffer. Otherwise, you will receive the verdict TLE. To flush the buffer, use:

• fflush(stdout) or cout.flush() in C++;
• flush(output) in Pascal;
• stdout.flush() in Python;
• refer to the documentation for other languages.

Input Format

See [Implementation Details].

Output Format

See [Implementation Details].

1

1

2

? 2

? 3

! 5

Hint

Constraints

It is guaranteed that

• $1\le T\le 100$;
• $m$ is a non-negative number, and $\textcolor{red}{0}\le m\le 10^{17}$。

Scoring

Let $Q$ be the maximum queries used in each test. The $\mathrm{score}$ is calculated as following:

$$\begin{aligned} \mathrm{score}=\begin{cases} 0, & Q\in [81,+\infty) \\ 10, & Q\in [11,81) \\ 25, & Q\in [3,11) \\ 50, & Q\in [0,3) \\ \end{cases} \end{aligned}$$

The score of this problem is the minimum score among all tests.