Description

哦不，这可恶的出题人又向你隐瞒了一些东西，你需要通过交互来猜出它。

这一次，你需要找到一个整数 $n$。为此，你可以进行最多 10 次查询，询问 $n!$（即从 1 到 $n$ 的所有整数的乘积，也称为阶乘）的第 $k$ 位十进制数字。

交互方式

第一行是一个整数 $t$ ($1 \le t \le 100$)——你需要处理的测试数据组数。

对于每组测试，整数 $n$ 是预先选定的。$n!$ 的长度最多为 $20\,000$，因此 $1 \le n \le 5982$。

你可以进行最多 10 次形如“$\tt{? }$ $k$” ($0 \le k < 20\,000$) 的查询。作为对查询的回应，你将得到一个数字——$n!$ 的第 $k$ 位十进制数字（回应介于 0 和 9 之间，包含两端）。数字从 0 开始编号，从最低有效位开始。如果 $n!$ 太短，没有第 $k$ 位数字，则返回 0。

当你的程序找到 $n$ 的值后，应以“$\tt{! }$ $n$”的形式作答。如果答案正确，你将收到“$\tt{YES}$”，并应继续处理下一组测试，或者如果这是最后一组则终止程序。如果答案不正确，或者你试图猜测，并且存在多个与你收到的信息一致的可能答案，你将收到“$\tt{NO}$”。在这种情况下，你的提交将获得“$\tt{Wrong\ answer}$”的评测结果，你的代码应立即终止。

Input Format

见交互方式。

Output Format

见交互方式。

2

1

YES

0

2

YES

? 0

! 1

? 0

? 19997

! 5982