Alice 有一个秘密整数 $y$，选自 $[1, 10^{18}]$。Bob 想要获取这个数字，因此他向 Alice 提出了一些问题。在每个问题中，Bob 给 Alice 一个 $[1, 10^{18}]$ 范围内的整数 $x$，Alice 返回 $0$（如果 $y < x$）、$1$（如果 $y = x$）或 $2$（如果 $y > x$）。

一切听起来都很完美，但 Alice 和 Bob 之间的通信被 Eve 篡改了！Eve 编写了一个随机数生成器 $\mathcal{H}$，用于生成 $0$ 到 $n - 1$ 之间的伪随机数。每当 Bob 提供一个数字时，Eve 都会调用 $\mathcal{H}$ 生成一个伪随机数 $x$，并将该 $x$ 与 Alice 返回的结果进行按位异或（XOR）运算后提供给 Bob。

Bob 发现 Alice 返回的结果被某人篡改了，因为他得到了相互矛盾的结果。通过某种手段，Bob 获取了 $\mathcal{H}$ 的源代码，如下所示。

图 1：$\mathcal{H}$ 的工作原理。

代码中指定了常量 $P$ 和 $n$，因此 Bob 也知道它们的值。但他对 $seed$ 一无所知，只知道篡改者 Eve 在交互过程中不会修改该值。你能帮助 Bob 在 100 次询问内获取 Alice 的秘密数字吗？

输入格式

第一行包含一个整数 $t$，表示测试用例的数量（$1 \le t \le 100$）。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $P$：$\mathcal{H}$ 中的两个常量。保证 $3 \le n \le 4$，$10 \le P \le 10^{18}$，且 $P$ 是一个质数。

交互

要进行询问，请输出一行格式为 “? $x$” 的内容（$1 \le x \le 10^{18}$）。然后，你应该读取一行作为回答。在每个测试用例中，你最多可以询问 100 次。

如果回答是一个非负整数，则它是 Bob 收到的数字，你可以继续猜测。如果回答为 $-1$，则意味着你超过了询问次数或进行了无效询问。收到 $-1$ 后请立即退出，你将看到 “Wrong Answer” 判决。否则，由于你的程序将继续从已关闭的流中读取，你可能会得到任意判决。

如果你已经得到了秘密数字 $y$，请输出一行格式为 “! $y$” 的内容。然后，你应该读取一行作为回答。

如果回答为 $-1$，则意味着你的猜测错误，你应该立即退出。如果回答为 $1$，则意味着你的猜测正确，你应该读取并解决下一个测试用例。注意，输出这个秘密数字不计入 100 次询问次数。

保证交互器是确定性的，这意味着交互器不会根据你的询问动态修改 $y$ 和 $seed$ 的值。

请记住，每次输出一行后，都要打印换行符并刷新输出。否则，你很可能会得到 “Idleness Limit Exceeded” 判决。

样例

样例输入 1

1
3 998244353
? 4
? 2
? 1
! 1

样例输出 1

0
0
1
1

说明

在样例中，$seed = 0$，因此 Bob 总是从 Alice 那里收到正确的答案。在这种情况下，Bob 直接使用二分查找是合理的，但这并不适用于其他可能的情况。