题目描述

这是一道交互题。

你正在玩一款名为「乌蒙滴叉」的音乐游戏。在专家模式中，需要精确校准音符的击打时机参数，该参数是一个 $[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}$；

此外，其他的评测结果仍会在评测过程中根据通常情况返回。

输出格式

见输入格式。

2
1

8

1

1

0

0

! 1

? 6

? 4

? 2

? 3

! 3

提示

在第一组测试用例中，可以唯一确定 $x = 1$，因此我们直接提交 $x' = 1$。

在第二组测试用例中，隐藏的参数 $x = 3$，交互过程如下：

• 测试 $y=6$，响应为 $y>x$ 为真；
• 测试 $y=4$，响应为 $y>x$ 为真；
• 测试 $y=2$，响应为 $y>x$ 为假；
• 测试 $y=3$，响应为 $y>x$ 为假；
• 提交 $x' = 3$。

请注意，此示例仅用于演示交互格式。不能保证提供的查询是最优的或唯一确定答案。