哦不,这个邪恶的陪审团又向你隐瞒了一些东西,你需要互动地猜测。
这次,你需要找到一个整数$$$n$$$。为此,您最多可以进行 10 次以下形式的查询:“从 1 到 $$$n$$$ 的所有整数的乘积的第 $$$k$$$ 小数位数是多少(也称为阶乘,表示为 $$$n!$$$)?”。
互动
在第一行中,有一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 您要处理的测试数量。
对于每个测试,都会提前选择整数 $$$n$$$。 $$$n!$$$ 的长度最多为 $$$20\,000$$$,因此 $$$1 \le n \le 5982$$$。
你可以 最多 10 条查询 的形式“? $$$k$$$" ($$$0 \le k \lt 20\,000$$$)。在响应查询时,您将得到一位数字 — $$$n!$$$ 的第 $$$k$$$ 小数位(响应介于 0 和 9 之间)。数字从 0 开始编号,从最低有效数字开始。如果 $$$n!$$$ 是太短,并且没有第 $$$k$$$ 位,则返回 0。
当你的程序找到 $$$n$$$ 的值后,它应该回答“! $$$n$$$"。如果答案正确,那么您将收到"是“并且应该继续下一个测试,如果是最后一个测试则终止。如果答案不正确,或者您试图猜测,并且有几个可能的答案与您收到的信息一致,您将得到“NO“。在这种情况下,您提交的内容将收到”错误答案“判决和您的代码应立即终止。
示例
输入复制
2 1 YES 0 2 YES
输出复制
? 0 ! 1 ? 0 ? 19997 ! 5982