这是一个交互式问题。

有人选择了一个正有理数 $x = p/q$，其中 $1 \le p, q \le 10^9$。你最多可以进行 10 次形如 “? $m$” 的询问，其中 $10^9 < m < 10^{12}$ 且 $m$ 是一个质数。对于每次询问，你将得到一个数字 $y$，满足 $y \equiv pq^{-1} \pmod{m}$。你需要猜出数字 $x$。

交互

输入的第一行包含一个整数 $t$，表示测试用例的数量 ($1 \le t \le 10^5$)。

对于每个测试用例，你最多可以进行 10 次询问。每次询问必须是以下两种类型之一：

1. “? $m$”，其中 $10^9 < m < 10^{12}$ 且 $m$ 是一个质数。
2. “! $p$ $q$”，其中 $1 \le p, q \le 10^9$，表示答案等于 $p/q$。

保证每个测试用例中的数字 $x$ 在测试过程中不会改变。

样例

样例输入 1

3
1
500000004
2

样例输出 1

? 1000000007
! 1 1
? 1000000007
! 2 4
? 1000000007
! 2 1

说明

在样例中，你处理的是 $x = 1/1$，$x = 1/2$ 和 $x = 2/1$，同时始终取 $m = 10^9 + 7$。 正如你所见，只要 $1 \le p, q \le 10^9$ 且 $x = p/q$，并不要求 $\gcd(p, q) = 1$。