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.