Description

This problem is differ from B1. 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.

Homura and Madoka are playing a game.

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

Madoka can ask Homura: for a non-negative integer $x$, what is the value of $x\bmod m$. Madoka aimed 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, Madoka is at the military training, so she turned to you.

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

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

The value of $m$ is read from input file and won't 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 $x\bmod m$ is available.

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

  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 outputting 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

0

1

? 5

? 1

! 5

Hint

Constraints

It is guaranteed that

• $1\le T\le 100$;
• $m$ is a positive ineteger, and $\textcolor{red}{2}\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 [101,+\infty) \\ 30, & Q\in [3,101) \\ 50, & Q\in [0,3) \\ \end{cases} \end{aligned}$$

The score of the task is the minimum score of each test.