题目描述

An integer $n$ is hidden ($1 \le n < 10^8$), and it is not divisible by $10$. Your task is to find this number.

You may ask queries of the following form: choose an integer $x$ ($1 \le x \le 10^9$). In response, you will receive the first digit of the number $n \cdot x$.

The first digit of a positive integer is its most significant digit in decimal notation. For example, the first digit of the numbers $7$, $42$, $123456$ is respectively $7$, $4$, $1$.

You need to find the hidden number $n$. You can use at most $28$ queries for each testcase.

输入格式

The first line contains two integers $t$ and $q$ ($1 \le t \le 10^3, q=28$) --- the number of testcases and the maximum number of queries that can be used in each testcase.

Interaction

In each testcase, a separate number $n$ is hidden.

To make a query, print $$\texttt{? } x$$, where $1 \le x \le 10^9$.

In response to a query, the jury program will print one integer $d$ ($1 \le d \le 9$) --- the first digit of the number $n \cdot x$.

After printing a query, do not forget to print a newline and flush the output buffer. Otherwise, you will receive the verdict $\tt{Time limit exceeded}$. To flush the buffer, use:

• $\tt{fflush(stdout)}$ or $\tt{cout.flush()}$ in C++;
• $\tt{System.out.flush()}$ in Java;
• $\tt{flush(output)}$ in Pascal;
• $\tt{stdout.flush()}$ in Python.

When you have determined the hidden number $n$, print $$\texttt{! } n$$.

After that, if this was the last testcase, you must terminate your program. Otherwise, you should continue the interaction with the next testcase.

$q$ is the maximum number of $\texttt{?}$ queries that your program may use in one testcase. Printing an answer of the form $\texttt{!}$ does not count as a query.

Note that if your query is invalid, the interactor will print $\texttt{-1}$ and terminate. A query is considered invalid if:

• $x$ does not satisfy the constraint $1 \le x \le 10^9$;
• the number of queries in the current testcase exceeded $q$;
• the answer $\texttt{! } n$ is incorrect.

If you read $\texttt{-1}$, immediately terminate your program to receive the verdict $\tt{Wrong answer}$ instead of an arbitrary verdict.

1 28
1
6

? 1
? 59
! 11

提示

Consider the example. Suppose that in this example it is additionally known that the hidden number is less than $100$.

After the query $x = 1$ and the answer $1$, we understand that the first digit of the hidden number is $1$.

After the query $x = 59$ and the answer $6$, we understand that the first digit of the product of the hidden number and $59$ is $6$.

Among all numbers less than $100$ that are not divisible by $10$, only the number $11$ satisfies both conditions. Therefore, the answer in the example is $11$.

Scoring

• ($2$ points): $n \le 10$;
• ($6$ points): $n \le 100$;
• ($7$ points): $n \le 1000$;
• ($8$ points): $n \le 10000$;
• ($10$ points): $n$ is a perfect square;
• ($10$ points): $n \le 10^5$;
• ($11$ points): $n \le 10^6$;
• ($12$ points): $n \le 10^7$;
• ($14$ points): $n \le 5 \cdot 10^7$;
• ($20$ points): no additional constraints.

A solution passes a subtask only if it correctly finds the number $n$ for every testcase of that subtask, using no more than $q$ queries in each one.