Description

这是一道交互题。

具体来说，有一个神秘的正整数 $h\ (1\le h < 2^{60})$，你需要通过不超过 $\lfloor \log_2 h\rfloor+3$ 次询问来猜出这个数。每次询问可以向小 L 提出两个数字 $a$ 和 $b\ (1\le a, b < 2^{61})$，她会告诉你 $\gcd(a, h + b)$ 的值。

交互库是非自适应的。也就是说，$h$ 在交互开始前就已经固定。

注：

• $\lfloor x \rfloor$ 代表不超过 $x$ 的最大整数，例如 $\lfloor 1.1 \rfloor=1,\ \lfloor 2.0 \rfloor=2$。

• $\gcd(a,b)$ 代表 $a$ 和 $b$ 的最大公因数，例如 $\gcd(10,15)=5$。

交互格式

每次询问输出 ? a b，代表你向小 L 询问的数，之后读入一个数 $g$ 代表 $\gcd(a, h + b)$。

如果你已经猜出了这个神秘数 $h$，输出 ! h，代表你的答案。

每次输出之后，你需要清空缓冲区，清空输出缓冲区可以使用以下方式：

• C/C++：fflush(stdout)（如果您使用 printf），cout.flush() 或 cout << endl（如果您使用 cout）

• Java：System.out.flush()

• Pascal：flush(output)

• Python：sys.stdout.flush()

交互格式示例：

cout << "? " << a << " " << b << '\n';//一次询问
cout.flush();//刷新缓冲区
long long g; cin >> g;//读入g
cout << "! " << h << '\n';//输出答案
cout.flush();//刷新缓冲区

Input Format

本题有多组数据。第一行一个正整数 $T\ (1\le T\le10^3)$，表示数据组数。

对于每组数据：

见「交互格式」。

Output Format

对于每组数据：

见「交互格式」。

2

2

3

1

10

7

? 2 2

? 3 2

! 520

? 2 1

? 10 6

? 7 2

! 1314

Hint

注：样例仅展示交互格式。

如果返回的 $h$ 不正确，会判为 Wrong Answer。

如果询问的数 $a$ 或 $b$ 不在 [1, $2^{61}$) 范围内，可能会被判为 Wrong Answer 或 Time Limit Exceeded。

如果询问次数超过 $\lfloor \log_2 h\rfloor+3$ 次，会判为 Wrong Answer 或 Time Limit Exceeded，所以请一定要及时返回答案。

结语：

但故事总会结束。

飞花不似当年，胜似当年。
新愁哀怨醉亭前，一轮孤月，一行飞雁
——月雩, 乙巳(2025)年九月二十三日作