CF1773I.Interactive Factorial Guessing

哦不，这个狡猾的评测系统又对你隐瞒了一些信息，你需要通过交互的方式来猜测它。

这一次，你需要找出一个整数 $n$。为此，你最多可以进行 10 次查询，查询的形式为：“$n!$（即从 1 到 $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 开始编号，0 表示最低位。如果 $n!$ 太短，没有第 $k$ 个数字，则返回 0。

当你的程序确定了 $n$ 的值后，应输出 "! $n$"。如果答案正确，你将收到 "YES"，然后进入下一个测试用例，或者如果已经是最后一个测试用例则终止。如果答案不正确，或者你尝试猜测时存在多个与已知信息一致的可能答案，你将收到 "NO"。此时，你的提交将立即被判为“Wrong answer”，程序应立即终止。

由 ChatGPT 4.1 翻译