Guess the Number#527

Guess the Number

1 second
256 megabytes
Very hard

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

You may ask queries of the following form: choose an integer (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 , , is respectively , , .

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

Input

The first line contains two integers and (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 is hidden.

To make a query, print «», where 1 \le x \le 10^9.

In response to a query, the jury program will print one integer (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 Time limit exceeded. To flush the buffer, use:

  • fflush(stdout) or cout.flush() in C++;

  • System.out.flush() in Java;

  • flush(output) in Pascal;

  • stdout.flush() in Python.

When you have determined the hidden number , print «».

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

is the maximum number of «?» queries that your program may use in one testcase. Printing an answer of the form «!» does not count as a query.

Note that if your query is invalid, the interactor will print «-1» and terminate. A query is considered invalid if:

  • does not satisfy the constraint 1 \le x \le 10^9;

  • the number of queries in the current testcase exceeded ;

  • the answer «! n» is incorrect.

If you read «-1», immediately terminate your program to receive the verdict Wrong answer instead of an arbitrary verdict.

Examples

Example 1

Loading
Loading

Note

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

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

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

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

Scoring

  1. ( points): n \le 10;

  2. ( points): n \le 100;

  3. ( points): n \le 1000;

  4. ( points): n \le 10000;

  5. ( points): is a perfect square;

  6. ( points): n \le 10^5;

  7. ( points): n \le 10^6;

  8. ( points): n \le 10^7;

  9. ( points): n \le 5 \cdot 10^7;

  10. ( points): no additional constraints.

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