题目描述

有一个隐藏的整数 $n$ ($1 \le n < 10^8$)，且 $n$ 不被 $10$ 整除。你的任务是找出这个数。

你可以提出如下形式的询问：选择一个整数 $x$ ($1 \le x \le 10^9$)。作为回答，你将得到数 $n \cdot x$ 的首位数字。

一个正整数的首位数字是指其十进制表示中最靠左的那一位数字。例如，数 $7$、$42$、$123456$ 的首位数字分别是 $7$、$4$、$1$。

你需要找出隐藏的整数 $n$。对于每个测试用例，你至多可以使用 $28$ 次询问。

输入格式

第一行包含两个整数 $t$ 和 $q$ ($1 \le t \le 10^3, q=28$) —— 测试用例的数量以及每个测试用例中允许使用的最大询问次数。

交互方式

在每个测试用例中，都隐藏着一个独立的数 $n$。

若要发起询问，请输出 $$\texttt{? } x$$，其中 $1 \le x \le 10^9$。

作为对询问的回应，裁判程序会输出一个整数 $d$ ($1 \le d \le 9$) —— 数 $n \cdot x$ 的首位数字。

在输出询问后，请不要忘记输出一个换行符并刷新输出缓冲区。否则，你将收到 $\tt{Time\ limit\ exceeded}$（超出时间限制）的判决。要刷新缓冲区，请使用：

• C++ 中的 $\tt{fflush(stdout)}$ 或 $\tt{cout.flush()}$；
• Java 中的 $\tt{System.out.flush()}$；
• Pascal 中的 $\tt{flush(output)}$；
• Python 中的 $\tt{stdout.flush()}$。

当你确定隐藏的数 $n$ 后，请输出 $$\texttt{! } n$$。

在此之后，如果这是最后一个测试用例，你必须终止你的程序。否则，你应当继续与下一个测试用例进行交互。

$q$ 是你的程序在一个测试用例中最多可以使用的 $\texttt{?}$ 询问次数。输出形如 $\texttt{!}$ 的答案不计入询问次数。

请注意，如果你的询问不合法，交互器会输出 $\texttt{-1}$ 并终止程序。询问在以下情形下被认为不合法：

• $x$ 不满足约束 $1 \le x \le 10^9$；
• 当前测试用例中的询问次数超过了 $q$；
• 答案 $\texttt{! } n$ 不正确。

如果你读到了 $\texttt{-1}$，请立即终止你的程序，以便收到 $\tt{Wrong\ answer}$（答案错误）的判决，而非其他不可预期的判决。

1 28
1
6

? 1
? 59
! 11

提示

考虑这个例子。假设在该例子中额外已知隐藏的数小于 $100$。

在询问 $x = 1$ 并得到回答 $1$ 后，我们得知隐藏数的首位数字是 $1$。

在询问 $x = 59$ 并得到回答 $6$ 后，我们得知隐藏数与 $59$ 的乘积的首位数字是 $6$。

在所有小于 $100$ 且不被 $10$ 整除的数中，只有 $11$ 同时满足这两个条件。因此，样例中的答案为 $11$。

计分

• （$2$ 分）：$n \le 10$；
• （$6$ 分）：$n \le 100$；
• （$7$ 分）：$n \le 1000$；
• （$8$ 分）：$n \le 10000$；
• （$10$ 分）：$n$ 是完全平方数；
• （$10$ 分）：$n \le 10^5$；
• （$11$ 分）：$n \le 10^6$；
• （$12$ 分）：$n \le 10^7$；
• （$14$ 分）：$n \le 5 \cdot 10^7$；
• （$20$ 分）：无额外限制。

一个解答仅当对其所属子任务中的每一个测试用例，都能在不超过 $q$ 次询问的条件下正确找出数 $n$，才算通过该子任务。

翻译由 DeepSeek V4 Pro 完成