这是一个交互问题。
有一个正整数 $$$1 \le x \le 10^9$$$ 你必须猜测。
在一个查询中,您可以选择两个正整数 $$$a \neq b$$$。作为此查询的答案,您将得到 $$$\gcd(x + a, x + b)$$$,其中 $$$\gcd(n, m)$$$ 是数字 $$$n$$$ 和 $$$m$$$ 的最大公约数。
要猜测一个隐藏数字 $$$x$$$,您最多可以进行 $$$30$$$ 查询。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) 表示测试用例的数量。
您必须猜测的整数 $$$x$$$ 满足约束:($$$1 \le x \le 10^9$$$)。
互动
隐藏数字 $$$x$$$ 在交互开始之前是固定的,不取决于您的查询。
要猜测每个 $$$x$$$,您可以通过以下方式进行不超过 $$$30$$$ 查询:
- "? a b" ($$$1 \le a, b \le 2 \cdot 10^9$$$, $$$a \neq b$$$)。
对于此查询,您将得到 $$$\gcd(x + a, x + b)$$$。
当你知道 $$$x$$$ 时,按以下格式打印一行。
- “!x”($$$1 \le x \le 10^9$$$)。
之后继续解决下一个测试用例。
如果您对一个 $$$x$$$ 提出超过 $$$30$$$ 查询或提出无效查询,则交互器将立即终止,并且您的程序将收到错误答案的判决。
打印每个查询后,不要忘记输出行尾并刷新输出缓冲区。否则,您将得到超出空闲限制的判决。要进行冲洗,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 阅读其他语言的文档。
黑客
要使用 hack,请使用以下测试格式:
第一行应包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例的第一行也是唯一一行应包含一个整数 $$$x$$$ ($$$1 \le x \le 10^9$$$) 表示应该猜测的整数 $$$x$$$。
示例
输入 #1
2 1 8 1
输出 #1
? 1 2 ? 12 4 ! 4 ? 2000000000 1999999999 ! 1000000000
注意
第一个隐藏数字是 $$$4$$$,这就是为什么查询的答案是:
“?1 2”—$$$\gcd(4 + 1, 4 + 2) = \gcd(5, 6) = 1$$$。
"? 12 4" — $$$\gcd(4 + 12, 4 + 4) = \gcd(16, 8) = 8$$$。
第二个隐藏数字是 $$$10^9$$$,这就是为什么查询的答案是:
“?2000000000 1999999999”—$$$\gcd(3\cdot 10^9, 3\cdot 10^9 - 1) = 1$$$。
这些查询只是为了理解交互,不足以找到真正的$$$x$$$。