这是一个交互式问题。

你站在一个潮湿、发霉、阴雨绵绵的地方，无人理睬，唱着一首没有听众的歌，等待着那个人的出现。

终于，她从拐角处走了进来。这一次，她没有“徘徊片刻便离去”，而是邀请你一起面对结局……

此时，在崩塌的天空中出现了一个长度为 $n$ 的密码锁 $a$。每个数字 $a_i$ 都在 $[1, n]$ 范围内。保证初始时，并非所有的 $a_i$ 都相等。你现在可以执行以下操作：

• 选择一个下标 $pos$ ($1 \le pos \le n$)。你可以将第 $pos$ 个拨盘向前拨动 1 步（即 $a_{pos} \to (a_{pos} \bmod n) + 1$）。然后，你将被告知数组中是否存在任何与 $a_{pos}$ 相等的数（不包括 $a_{pos}$ 自身）。

当所有数字都相等时（它们不一定非要变成 1），密码锁即被解开。

世界末日正在迅速逼近。你必须在 $\lceil \frac{3n(n+1)}{2} \rceil$ 次操作内解开这个密码锁，以防止世界毁灭。

交互

本题包含多个测试用例。首先，你的程序必须从标准输入中读取一个整数 $T$ ($1 \le T \le 100$)。

在单个测试用例中：

首先，你的程序从标准输入中读取一个整数 $n$ ($3 \le n \le 100$)。

然后，你可以使用格式 ? pos 执行操作。交互器将返回 0 或 1，表示数组中是否存在与 $a_{pos}$ 相等的数（0 表示没有，1 表示有）。如果你执行了非法操作或使用了超过 $\lceil \frac{3n(n+1)}{2} \rceil$ 次操作，你将读入 -1，在这种情况下，你应该立即终止程序以避免未定义的结果。

当你认为你已经解开了密码锁，你必须输出 ! 并直接进入下一个测试用例。这不计入操作次数。如果在任何测试用例中你未能解开密码锁，你的解答将被判定为 Wrong Answer。

保证 $\sum n \le 10^3$。

在打印查询后，不要忘记输出换行并清空缓冲区（flush）。否则，你将获得 Idleness limit exceeded 或 Time Limit Exceeded。为此，请使用：

• C++ 中的 fflush(stdout) 或 cout.flush()；
• Java 中的 System.out.flush()；
• Pascal 中的 flush(output)；
• Python 中的 stdout.flush()。

样例

输入样例 1

1
4
1
1
0
1

输出样例 1

? 1
? 3
? 4
? 4
!

说明

样例中的数组为 $a = [1, 2, 1, 4]$。

该样例仅用于演示交互过程。