P12531 [XJTUPC 2025] Beat Verdict: Precision Strike

**这是一道交互题。** 你正在玩一款名为「乌蒙滴叉」的音乐游戏。在专家模式中，需要精确校准音符的击打时机参数，该参数是一个 $[1,n]$ 内的神秘正整数 $x$。 为了确定这个参数，你可以进行至多 $4$ 次校准测试。每次测试时，你选择一个正整数测试值 $y$ ($1 \le y \le n$)，系统将告知你 $y > x$ 是否成立。最终你需要给出一个正整数参数估计值 $x'$ ($1 \le x' \le n$)，且满足 $x' \in \left[0.5x, 2x\right]$。 注意：最终给出的估计值 $x'$ 不计入上述至多 $4$ 次测试次数。

输入包含多个测试用例。数据的第一行包含一个整数 $t$ ($1\le t\le 500$) 表示测试用例数。每个测试用例的交互流程在下文中描述。 在每个测试用例中，输入的第一行包含一个正整数 $n$ ($1\le n \le 5 \times 10^9$)，表示参数的可能范围。 若你想进行测试，输出 `? y` ($1 \le y \le n$)。然后你读入对该测试的响应，为一个整数 $a$ ($a \in \{0, 1\}$)，$\tt{1}$ 表示 $y>x$ 为真，$\tt{0}$ 表示 $y>x$ 为假。 若你想提交参数 $x'$，输出 `! x'` ($1 \le x' \le n$)。然后你立即结束本个测试用例的交互，并准备下一个测试用例的交互。这次交互不计入上述至多 $4$ 次测试次数。 注意在你的程序每轮输出结束时（即，每一次输出 `? y` 或 `! x'` 后），**需要输出回车并刷新输出缓冲区**，否则你将会得到 $\tt{Time\ Limit\ Exceeded}$。 你可以使用： - C 的 `fflush(stdout)`； - C++ 的 `cout.flush()`； - Java 的 `System.out.flush()`； - Python 的 `stdout.flush()`； 来刷新输出缓冲区。 请注意：交互库自适应，即每个测试用例中的正整数 $x$ ($1 \le x \le n$) **可能会随着你的输入而变化**，但始终满足所有已经发生过的询问。 如果你最后输出的答案正确，你会得到 $\tt{Accepted}$； 如果你给出的询问不符合题目范围要求，或最后输出的答案不正确，你会得到 $\tt{Wrong\ Answer}$； 此外，其他的评测结果仍会在评测过程中根据通常情况返回。

见输入格式。

在第一组测试用例中，可以唯一确定 $x = 1$，因此我们直接提交 $x' = 1$。 在第二组测试用例中，隐藏的参数 $x = 3$，交互过程如下： - 测试 $y=6$，响应为 $y>x$ 为真； - 测试 $y=4$，响应为 $y>x$ 为真； - 测试 $y=2$，响应为 $y>x$ 为假； - 测试 $y=3$，响应为 $y>x$ 为假； - 提交 $x' = 3$。 请注意，此示例仅用于演示交互格式。不能保证提供的查询是最优的或唯一确定答案。