T510969 Strange Madoka Game (English ver.)
题目背景
[Chinese statement](https://www.luogu.com.cn/problem/T469282). **You must submit your code at the Chinese version of the statement.**
题目描述
**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.
输入格式
无
输出格式
无
说明/提示
#### 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.