题目背景

English statement. You must submit your code at the Chinese version of the statement.

伝えたいコトバは たったひとつ / 想要传达的言语 唯有一个
キミがいたから 強くなれた / 因有你在 我变坚强了
2 人ならどんな空も飛べるね / 只要两人一起就能任意飞翔
キミをいつでも 信じてるから / 因为一直都 坚信着你
ずっとずっと夢を見ていよう / 能同做此梦不复醒吧

题目描述

本题和 B1 是不同的问题，请分别仔细阅读两题题面。

这是一道交互题。

提示：我们在题目描述的最后提供了一份简要的、形式化描述的题面。

焰和圆在玩游戏。

焰在心中想了一个正整数 $m$，让圆猜出 $m$ 的值。当然，焰不会为难圆，所以 $\textcolor{red}{2}\le m\le 10^{17}$。焰不会作弊，也就是说，焰不会悄悄更换想好的数字。

圆可以问焰：对于非负整数 $x$，$x\bmod m$ 的值是多少。圆需要用最少的询问次数来猜出 $m$ 的值。（为了得到全部分数，最多只能使用 $2$ 次询问。）

焰一共和圆玩了 $T$ 次游戏。圆的数学很好，在 $\varepsilon$ 秒内就秒了这题，但是她在军训，于是她找来了你，来帮她猜出这 $T$ 次游戏的答案。

形式化地：有一个隐藏的正整数 $m\in [\textcolor{red}{2},10^{17}]$。每次询问给定非负整数 $x$，回答 $x\bmod m$。用最少的询问次数找出 $m$。共有 $T$ 组测试数据。$m$ 的数值在事先确定，不会根据询问变化，也就是说，交互库是非适应性的。

【实现细节】

对于每个测试点，输入一行一个正整数 $T$，表示游戏次数。

对于每组测试数据，你可以用以下的格式发起一次询问：

• $\texttt{? }x$：询问 $x\bmod m$ 的值。你需要保证 $x$ 是非负整数，且 $x \in \textcolor{red}{ [0,10^{18}]}$。

  从标准输入流读入一个整数表示答案。特别地，若整数是 $\texttt{-1}$，你的程序已经被判定为 $\texttt{Wrong Answer}$，此时你需要立刻终止程序。

你可以用以下的格式回答答案：

• $\texttt{! }m$：回答 $m$ 的值。

在发起询问后，需要刷新缓冲区，否则可能导致 TLE。

• 在 C++ 中，使用 fflush(stdout) 或 cout.flush()。 特别地，利用 std::endl 来换行也会刷新缓冲区。
• 在 Pascal 中，使用 flush(output)。
• 在 Python 中，使用 stdout.flush()。
• 对于其它语言，可自行查阅文档。

输入格式

见【实现细节】。

输出格式

见【实现细节】。

1

0

1

? 5

? 1

! 5

提示

数据范围

对于 $100\%$ 的数据，保证 $1\le T\le 100$，$m$ 为正整数，$\textcolor{red}{2}\le m\le 10^{17}$。

评分方式

记单个测试点中，你的询问次数的最大值为 $Q$。则得分 $\mathrm{score}$ 如下所示：

$$\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} $$

本题得分为所有测试点得分的最小值。