题目描述

题目译自 BalticOI 2020 Day1 A「Colors」

Linda 是一个具有强烈的傲娇色彩的女孩。
她十分喜欢随心所欲地染发，还会因男友 Archie 注意到她发色的变化而窃喜。
当且仅当 Archie 注意到 Linda 发色的变化时，他会对此作出评论 —— 所以 Linda 总能轻易地知道 Archie 是否发现了这一点。

近日，市场上出现了新的一个发色系列。其中所有颜色以 $1\dots N$ 编号，满足两种颜色数值差异越小，视觉差异便越小。

Linda 认为，在这个系列中存在某个关键颜色差 $C\ (1 \le C \le N)$。
它意味着，对于任意当前颜色 ${\rm color}_{\rm new}$ 和上一个颜色 ${\rm color}_{\rm prev}$，当且仅当 $|{\rm color}_{\rm new} - {\rm color}_{\rm prev}| \ge C$ 时，Archie 会注意到它们的差异。

现在 Linda 购置了这个系列中的 $N$ 套发色 —— 每一个都是 $1\dots N$ 中的一种颜色，并准备进行一场实验。
她将定期更换她的发色并观察 Archie 的反应 —— 即他是否察觉发色的变化。
为了正确的发色，每一套发色都要被使用，所以不会有某套发色出现超过一次。

在实验开始之前，Linda 仍会使用一款与实验所用发色毫不相容的色彩，所以 Archie 对第一个被使用的发色的反应对于实验毫无意义。

她的目标是找到 $C$ 的确切值。
请你写出程序通过使用给定的 $N$ 个颜色进行实验并观察 Archie 的反应求出 $C$ 的值。

交互方式

这是一道交互题，并且与原题交互方式有细微区别。

输入的第一行包含一个整数 $T$，表示需要处理独立 $T$ 组数据。

对于每组数据，第一行包含一个整数 $N$，$C$ 的值会被交互器保留。

接下来，你的程序需要按如下格式输出询问到标准输出（符号和数字之间有一个空格分隔）：

• $\texttt{?}\ P$：整数 $P\ (1\le P\le N)$ 表示下一次要使用的颜色。
  对于每次询问，交互器会输出一行一个整数到标准输入。如果 Archie 注意到了最后两个颜色的差异，则输出 $1$，否则输出 $0$。任意两个询问的 $P$ 值不能相同。

当你的程序已经确定了 $C$ 值，你应该按如下格式输出它的值：

• $\texttt{=}\ C$
  输出后交互器不会响应，并进入下一组数据的交互。

若某组答案错误或交互失败，整个交互过程将立即停止。

请注意，为了保证交互过程正确，对于你的所有询问与回答，都应该刷新输出缓冲区。命令如下：

注：$\texttt{std::endl}$ 会输出换行并刷新缓冲区。

样例交互

数据范围与提示

对于每组数据，你的程序最多可以使用 $64$ 次 $\texttt{?}$ 来进行查询，以找到正确的 $C$ 值。

对于所有测试点，$1\le T\le 1200,1\le N\le 10^{18}$。

详细子任务及附加限制如下表：