噢不，邪恶的评测组又藏了什么东西让你猜，你需要通过交互的方式把它找出来。

这一次，你需要找到一个整数 $n$。为了做到这一点，你最多可以进行 10 次询问，询问形式为“从 1 到 $n$ 的所有整数的乘积（也称为阶乘，记作 $n!$）的第 $k$ 位十进制数字是什么？”。

交互

第一行包含一个整数 $t$ ($1 \le t \le 100$)，表示你需要处理的测试用例数量。

对于每个测试用例，整数 $n$ 是预先选定的。$n!$ 的长度不超过 $20\,000$，因此 $1 \le n \le 5982$。

你可以进行最多 10 次形式为 “? k” ($0 \le k < 20\,000$) 的询问。作为对询问的响应，你将得到一个数字 —— $n!$ 的第 $k$ 位十进制数字（响应在 0 到 9 之间）。数字从 0 开始编号，从最低有效位开始。如果 $n!$ 的长度不足，不存在第 $k$ 位，则返回 0。

在你的程序找到 $n$ 的值后，应输出 “! n”。如果答案正确，你将收到 “YES”，并应继续处理下一个测试用例，或者如果是最后一个测试用例则终止程序。如果答案不正确，或者你试图猜测，且存在多个与你已收到的信息一致的可能答案，你将收到 “NO”。在这种情况下，你的提交将获得 “Wrong answer” 判决，且你的代码应立即终止。

样例

输入 1

2
1
YES
0
2
YES

输出 1

? 0
! 1
? 0
? 19997
! 5982