Description

【这是一道交互题】

定义 $f(x)$ 表示严格大于 $x$ 的最小的完全平方数，定义 $g(x)$ 为小于等于 $x$ 的最大的完全平方数。例如，$f(1)=f(2)=g(4)=g(8)=4$。

一个正整数是“可爱”的，当且仅当 $x-g(x)<f(x)-x$，例如，$1,5,11$ 是可爱的正整数，而 $3,8,15$ 不是。

为了倾听小神灵的愿望，主角组需要向神子询问。小神灵有一个最喜欢的正整数 $a$，神子可以根据灵梦给出的 $x\quad(x\in[0,10^9])$，向小神灵询问，而小神灵只能回答她，$a+x$ 是不是可爱的正整数（$\text{cute number}$）。

请通过适当的询问找出 $a$。

Input Format

第一行有一个正整数 $T$，表示数据组数。每一组之间互相独立。

接下来，对于每一组数据，你将可以进行以下两种操作：

• $\verb!? x!$：询问 $a+x$ 是否是 $\text{cute number}$。要注意，$x$ 的值应当在 $[0,10^9]$ 以内。对于正确的询问，交互库会返回一个数字 $1$ 或者 $0$，表示 $a+x$ 是/不是 $\text{cute number}$。
• $\verb|! a|$：报告你发现的 $a$。如果你给出的 $a$ 正确，该组数据结束。注意：报告操作不计入询问操作的总次数。

如果你的询问次数超过了 $100$，或者 $x$ 不符合数据范围，或者你报告的 $a$ 不正确，交互库会返回一个数字 $-1$。此时你应当立即结束程序，否则可能发生不可预知的错误。

1

1

1

1

1

1

0

0

1

? 0

? 1

? 2

? 3

? 10

? 100

? 233

? 1919810

! 114514

Hint

样例解释

样例当中的过程仅供参考。

样例当中，$a=114514$，是 $\text{cute number}$（因为 $338^2\le 114514 <339^2$，而 $114514-338^2=270<339^2-114514=407$）。

同样地，$a+0,a+1,a+2,a+3,a+10$ 均为 $\text{cute number}$。而 $a+100=114614$ 不是 $\text{cute number}$，因为 $338^2\le 114614 <339^2$，而 $114614-338^2=370\ge 339^2-114614=307$。

数据范围及约定

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|}\hline \textbf{Subtask} & \bm{a\le } & \bm{T\le} & \textbf{特殊性质} & \textbf{分值}\\\hline 1 & 100 & 100 & - & 10\\\hline 3 & 10^9 & 2\times 10^3 & - & 20\\\hline 2 & 10^{12} & 2\times 10^3 & \textbf{A} & 30\\\hline 4 & 10^{12} & 2\times 10^3 & - & 40\\\hline \end{array}$$

特殊性质 $\textbf{A}$：保证 $a$ 是 $\text{cute number}$。

对于全部数据，保证 $1\le a\le 10^{12}$。你发起的询问当中，$x$ 的值应当在 $[0,10^9]$ 以内。

---

此外，你每个测试点的得分还与该测试点所有询问次数的最大值有关。具体而言，设某个测试点你询问操作一共进行了 $\text{max\_count}$ 次。

• 若 $\text{max\_count}< 64$，你将获得该测试点 $100\%$ 的分数；
• 若 $64\le \text{max\_count}< 81$，你将获得该测试点 $50\%$ 的分数；
• 若 $81\le \text{max\_count}< 100$，你将获得该测试点 $20\%$ 的分数；
• 若 $\text{max\_count}\ge 100$，你将不能获得该测试点的分数。