题目描述

Linda 喜欢时不时改变她头发的颜色，如果她的男友 Archie 注意到她头发颜色发生了改变，Linda 会十分高兴。当且仅当 Archie 发现 Linda 的头发颜色发生改变时，Archie 才会去评论 Linda 头发的新颜色。这意味着 Linda 始终可以知道 Archie 是否发现她的头发颜色有改变。

现在市场上有一个新染发剂系列，该染发剂系列有 $N$ 种颜色，从 $1$ 到 $N$ 编号。两个颜色的相近程度与它们编号的差值有关——差值越小，则越相近。

Linda 发现，对于该系列的染发剂，存在一个色差阈值 $C$（$1 \leq C \leq N$）。具体来说，假如 Linda 之前使用的染发剂颜色编号为 $color_{prew}$，Linda 接下来打算使用的染发剂颜色编号为 $color_{new}$，则 Archie 会注意到 Linda 的颜色头发差异，当且仅当 $\left | color_{new}-color_{prew}\right | \geq C$。

现在 Linda 买下了一套该系列的染发剂，准备做一个实验。她会不断地更换头发的颜色，并观察 Archie 是否注意到了头发颜色发生改变。因为染发剂有限，每种颜色的染发剂最多只能使用一次。

在实验开始之前，Linda 使用的是另外一个系列的染发剂，因此讨论第一次染发后 Archie 的反应是没有意义的。

现在 Linda 想要通过有限的时间找到阈值 $C$，请写一个程序帮助她完成这个任务。

交互方式

本题是一道交互题。

与原题不同的是，为了压缩数据组数，本题单个测试点中将包含多组数据。

输入第一行包含一个整数 $T$，表示该测试点的数据组数。

对于每组数据，你首先将读入一个整数 $N$，代表该系列染发剂的颜色数量。

接下来，你可以按如下形式输出来进行询问：? P。其中 $P$ 代表 Linda 下一次要使用的染发剂的颜色编号。你输出的 $P$ 需要满足 $1 \leq P \leq N$，且任意两次询问的 $P$ 均不相同。

在询问过后，你的程序将读入一个整数，若这个整数为 $1$，代表 Archie 注意到了 Linda 头发颜色的变化；若为 $0$，则表示他没有注意到颜色的变化。

当你确认了阙值 $C$ 后，按如下格式输出答案：= C。

如果答案正确，将会直接进入下一组数据的交互。

如果答案错误，交互器将直接终止你的程序。

对于每组测试数据，你的程序可以最多进行 $64$ 次询问（最后输出答案不算作询问）。

请注意，一般情况下程序的输出会存放在缓冲区中，为了确保你的输出能被交互库接收，请在输出一行之后刷新缓冲区。

• 对于 C++ 语言，可以使用 std::cout<<std::endl 来在输出换行的同时刷新缓冲区；
• 对于 Java 语言，可以使用 System.out.flush(); 来刷新缓冲区；
• 对于 Python 语言，可以使用 sys.stdout.flush() 来刷新缓冲区。

1
7

1

1

0

0

1

? 2

? 7

? 4

? 1

? 5

= 4

提示

样例解释

为了方便各位理解交互过程，部分行之间人为添加了空行。

下面依次解释每次询问过程：

1. 这一次询问的结果无意义。
2. 此次询问后有 $C \leq 5$；
3. 此次询问后有 $3 \lt C \leq 5$，这时候可以考虑检测差值为 $4$ 时的情况。但因为 $4+4=8$ 和 $4-4=0$ 都不合法，因此不再考虑这么做。
4. 此次询问后有 $3 \lt C \leq 5$。
5. 此次询问后有 $3 \lt C \leq 4$，即 $C=4$。

子任务

所有数据均满足：$1 \leq T \leq 1200$，$1 < N \leq 10^{18}$。

• 子任务 1（9 分）：$N \leq 64$；
• 子任务 2（13 分）：$N \leq 125$；
• 子任务 3（21 分）：$N \leq 10^3$；
• 子任务 4（24 分）：$N \leq 10^9$；
• 子任务 5（33 分）：无特殊限制。