CF1386A.Colors

Linda likes to change her hair color from time to time, and would be pleased if her boyfriend Archie would notice the difference between the previous and the new color. Archie always comments on Linda's hair color if and only if he notices a difference — so Linda always knows whether Archie has spotted the difference or not.

There is a new hair dye series in the market where all available colors are numbered by integers from $1$ to $N$ such that a smaller difference of the numerical values also means less visual difference.

Linda assumes that for these series there should be some critical color difference $C$ ($1 \le C \le N$) for which Archie will notice color difference between the current color $\mathrm{color}_{\mathrm{new}}$ and the previous color $\mathrm{color}_{\mathrm{prev}}$ if $\left|\mathrm{color}_{\mathrm{new}} - \mathrm{color}_{\mathrm{prev}}\right| \ge C$ and will not if $\left|\mathrm{color}_{\mathrm{new}} - \mathrm{color}_{\mathrm{prev}}\right| \lt C$.

Now she has bought $N$ sets of hair dye from the new series — one for each of the colors from $1$ to $N$, and is ready to set up an experiment. Linda will change her hair color on a regular basis and will observe Archie's reaction — whether he will notice the color change or not. Since for the proper dye each set should be used completely, each hair color can be obtained no more than once.

Before the experiment, Linda was using a dye from a different series which is not compatible with the new one, so for the clearness of the experiment Archie's reaction to the first used color is meaningless.

Her aim is to find the precise value of $C$ in a limited number of dyes. Write a program which finds the value of $C$ by experimenting with the given $N$ colors and observing Archie's reactions to color changes.

Interaction

This is an interactive task. In the beginning you are given a single integer $T$ ($1 \leq T \leq 100$), the number of cases in the test.

For each test case, the input first contains a single integer — the value of $N$ ($1 \lt N \le 10^{18}$). The value of $C$ is kept secret by the grading system.

Then your program should make queries writing output in the following format: "? $P$", where $P$ is an integer ($1 \le P \le N$) denoting the next color used. For each query the grading system gives an answer in the next line of the input. The answer is $1$ if Archie notices the color difference between the last two colors and $0$ otherwise. No two queries should have the same $P$ value.

When your program determines $C$, it should output its value in the following format: "= $C$". The grading system will not respond to this output and will proceed with the next test case.

Your program may use at most 64 queries "?" for each test case to find the correct value of $C$.

To establish proper communication between your program and the grading system, you should flush the output stream after each query.

\\begin{array}{ll} \\text{Language} & \\text{Command} \\\\ \\hline \\text{C++} & \\texttt{std::cout }\\texttt{ \\lt }\\texttt{ \\lt }\\texttt{ std::endl;} \\\\ \\text{Java} & \\texttt{System.out.flush();} \\\\ \\text{Python} & \\texttt{sys.stdout.flush()} \\end{array}$$ Flush commands Note that std::endl writes a newline and flushes the stream. It is possible to receive an "Output isn't correct" outcome even after printing a correct answer, if task constraints were violated during the communication. Violating the communication protocol itself may result in an "Execution killed" outcome. Submitting user tests requires specifying an input file with the testcase parameters. The format of the input file is "$T$" in the first line, and then "$N$ $C$" on a single line for each of the $T$ cases. Scoring Subtasks: 1. (9 points) $N \le 64$ 2. (13 points) $N \le 125$ 3. (21 points) $N \le 1000$ 4. (24 points) $N \le 10^9$ 5. (33 points) No further constraints. 琳达喜欢时不时地改变自己的发色，如果她的男朋友阿奇能注意到她新旧发色之间的差异，她会非常开心。阿奇仅在察觉到发色差异时才会对琳达的发色发表评论——因此琳达总能知道阿奇是否注意到了变化。 市场上新推出了一款染发剂系列，其中所有可选颜色均用 $1$ 到 $N$ 的整数编号，且数值差越小，视觉差异也越小。 琳达假设：对该系列染发剂而言，应存在某个临界颜色差异值 $C$（$1 \le C \le N$），使得当当前发色 $\mathrm{color}_{\mathrm{new}}$ 与上一次发色 $\mathrm{color}_{\mathrm{prev}}$ 满足 $\left|\mathrm{color}_{\mathrm{new}} - \mathrm{color}_{\mathrm{prev}}\right| \ge C$ 时，阿奇会注意到颜色差异；而当 $\left|\mathrm{color}_{\mathrm{new}} - \mathrm{color}_{\mathrm{prev}}\right| \lt C$ 时，则不会注意到。 目前她已购齐该系列全部 $N$ 种染发剂——即从颜色 $1$ 到 $N$ 各一套，并准备开展实验。琳达将定期更换发色，并观察阿奇的反应（即他是否会注意到颜色变化）。由于每套染发剂必须一次性用完，因此每种发色最多只能使用一次。 实验开始前，琳达使用的是另一款不兼容的新系列的染发剂，因此阿奇对第一次使用的颜色的反应在本实验中无意义。 她的目标是在有限次数的染发尝试内，精确确定 $C$ 的值。请编写一个程序，通过在给定的 $N$ 种颜色上进行实验并观察阿奇对颜色变化的反应，来找出 $C$ 的准确值。 交互方式 本题为交互式题目。程序启动时，首先输入一个整数 $T$（$1 \leq T \leq 100$），表示测试用例的数量。 对每个测试用例，输入首先包含一个整数 $N$（$1 \lt N \le 10^{18}$）。真实 $C$ 值由评测系统保密。 随后，你的程序需通过输出查询语句进行提问，格式为：`? $P$`，其中 $P$ 是一个整数（$1 \le P \le N$），表示下一次使用的发色编号。对每次查询，评测系统将在下一行输入中返回一个答案：若阿奇注意到最近两次发色之间的差异，则回答 `1`；否则回答 `0`。任意两次查询所用的 $P$ 值不得重复。 当你的程序确定了 $C$ 的值，应按如下格式输出结果：`= $C$`。评测系统不会对此输出作出响应，并直接进入下一个测试用例。 你的程序在每个测试用例中至多可进行 64 次 `?` 查询以确定正确的 $C$ 值。 为确保你的程序与评测系统之间通信正常，每次查询后你都必须刷新输出流。 $$\begin{array}{ll} \text{语言} & \text{命令} \\ \hline \text{C++} & \texttt{std::cout } \texttt{ << } \texttt{ std::endl;} \\ \text{Java} & \texttt{System.out.flush();} \\ \text{Python} & \texttt{sys.stdout.flush()} \end{array}

刷新命令说明

注意：std::endl 会在输出换行符的同时刷新输出流。

即使输出了正确答案，若通信过程中违反了题目约束，仍可能收到 “Output isn't correct”（输出不正确）的判定结果。若违反交互协议本身，则可能导致 “Execution killed”（执行被终止）的结果。

提交用户自测时，需指定一个输入文件，其中包含测试用例参数。输入文件格式为：第一行为 $T$；随后 $T$ 行，每行包含两个整数 $N$ 和 $C$。

评分规则

子任务：

1. （9 分）$N \le 64$
2. （13 分）$N \le 125$
3. （21 分）$N \le 1000$
4. （24 分）$N \le 10^9$
5. （33 分）无额外限制

Comments to the example input line by line:

1. $N = 7$.
2. Answer to the first query is meaningless (can also be $0$).
3. $C \leq 5$.
4. $3 \lt C \leq 5$. It would be wise to check difference $4$. However, this can not be done in the next query since $4 + 4 = 8$ and $4 - 4 = 0$ both are outside the allowed interval $1 \le P \le 7$.
5. $3 \lt C \leq 5$.
6. $3 \lt C \leq 4$. Therefore, $C = 4$.

对示例输入逐行的注释：

1. $N = 7$。
2. 第一个查询的答案无意义（也可以为 $0$）。
3. $C \leq 5$。
4. $3 \lt C \leq 5$。此时检查差值 $4$ 是明智的。然而，由于 $4 + 4 = 8$ 和 $4 - 4 = 0$ 均超出了允许区间 $1 \le P \le 7$，因此无法在下一个查询中执行该操作。
5. $3 \lt C \leq 5$。
6. $3 \lt C \leq 4$。因此，$C = 4$。