「Wdoi-2」死亡之后愈发愉悦

**【这是一道交互题】** 定义 $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 第一行有一个正整数 $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$。此时你应当立即结束程序，否则可能发生不可预知的错误。 ## Background 落樱缤纷春不待，如果错过了这次机会，可能得等到紫藤绽放的春夏之际才能赏花了。 但是两人依然无心在樱花树下席地而宴。 因为正体不明的灵体在两人面前倏现骤消的飘浮着。 后来才明白这些四处飘浮的正体不明灵体，既非普通幽灵，也不是前阵子出现的怨灵。 这些是神灵。本应超脱为神的灵体。 一般而言，神灵多半居住在神社里，其实它们是随处可见的没有固定型态的灵体。 这些神灵让她们困惑不已。 超乎常人的强烈人欲、想法、恐惧与情感，是神灵出现的原因。一般而言，神灵很少危害人类，如果没有强烈的欲望。例如祈求丰收，或是除厄避邪等，是不会产生神灵的…… 小神灵指引着灵梦与魔理沙深入命莲寺的地底，与千年复苏的敌人交手。从命莲寺墓地到莲池中央的梦殿大祀庙，从彷徨的亡灵到极具传说色彩的圣德太子，从欲望加速到小小的欲望星空，一切都显得那么不可思议。 「死亡之后，才能得到更加绚烂的重生。」 [samples] ## Note ### 样例解释 样例当中的过程仅供参考。 样例当中，$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$，你将不能获得该测试点的分数。