这是一个交互式问题。

存在一个介于 $1$ 到 $10^{15}$（包含边界）之间的秘密正整数 $n$。

你可以询问以下类型的问题：“给定基数 $2 \le b \le 10^9$，整数 $n$ 在 $b$ 进制下的各位数字之和是多少？”你必须在不超过 $2$ 次询问内猜出 $n$。

交互

交互开始时，评测程序会发送一行包含测试用例数量 $t$ ($1 \le t \le 1000$) 的数据。

在每个测试用例中，交互由你的程序发送格式为 “? b” 的请求开始，其中 $b$ ($2 \le b \le 10^9$) 是表示 $n$ 的进制。评测程序会打印一行包含答案 $s$ 的数据，即 $n$ 在 $b$ 进制下的各位数字之和。当你准备好回答 $n$ 的值时，打印 “! n”。此操作不计入询问次数。

如果你使用的询问次数超过两次或你的答案不正确，你的提交将被拒绝，交互立即停止。否则，将开始下一个测试用例（如果这是最后一个测试用例，则交互结束）。

你可以假设对于每个测试用例，$n$ 的值在交互开始前是固定的（即交互器不是自适应的）。交互过程中涉及的所有整数（$b$、$s$ 和 $n$）均以十进制形式发送和接收。

样例

输入格式 1

1
2023
1

输出格式 1

? 1000000
? 2023
! 2023