Problem Description

This is an interactive problem.

MCPlayer542 has a mysterious odd prime $p$, but he does not want you to know what it is.

He plans to use a function $f(x)$ to encrypt his number. The value of $f(x)$ is the sum of the decimal digits of $x$. For example, $f(5)=5$, $f(542)=5+4+2=11$, and $f(1024)=1+0+2+4=7$.

However, since you are too smart, he thought about it and decided to change the encryption function to:

$$g(x)=f(f(f(f(f(f(f(f(f(f(x))))))))))$$

That is, apply $f(x)$ continuously $10$ times, and replace the $p$ in his hand with $q=p^k$.

Now he is going to give you $n$ integers $g(q^{a_1}),\ g(q^{a_2}),\ \ldots,\ g(q^{a_n})$, and he wants you to tell him what

$$q^{a_1}\bmod (m\cdot a_1),\ q^{a_2}\bmod (m\cdot a_2),\ \ldots,\ q^{a_n}\bmod (m\cdot a_n)$$

are, respectively. He thinks you definitely cannot guess it, so he decides to let you choose $m$ and $a_1,\ a_2,\ \ldots,\ a_n$ yourself. Can you complete this task?

Note: The range of $m$ has special constraints.

Input Format

The input contains multiple test cases. The first line contains an integer $t$ ($1\le t\le 500$), indicating the number of test cases. The interactive process for each test case is described below.

In each test case, the first line contains two integers $n$ and $k$ ($1\le n\le 50, \ 1\le k\le 10^9$), separated by a single space, with meanings as described in the statement.

Then, for each interaction, output one integer $a_i$ per line ($1\le a_i\le 10^{18},a_i$ are pairwise distinct), indicating the exponent of $q$ you want to query.

After making a query, you should read an integer, which is $g(q^{a_i})$.

After finishing $n$ rounds of interaction, you need to output one integer $m$ in one line ($m\ge 35,1\le m\cdot a_i\le 10^{18}$), then output $n$ numbers in the next line: $q^{a_1}\bmod (m\cdot a_1), \ q^{a_2}\bmod (m\cdot a_2), \ \ldots, \ q^{a_n}\bmod (m\cdot a_n)$, separated by single spaces, as the answer.

You must perform exactly $n$ rounds of interaction, then output the answer and terminate the program, otherwise you may get unpredictable results.

Note that at the end of each output in your program (that is, each time you output $a_i$ for an interaction, and when you finally output $m$ and the answers), you need to print a newline and flush the output buffer. Otherwise, you will get $\text{Idleness Limit Exceeded}$.

• In C: $\text{fflush(stdout)}$;
• In C++: $\text{cout.flush()}$;
• In Java: $\text{System.out.flush()}$;
• In Python: $\text{stdout.flush()}$;

to flush the output buffer.

It is guaranteed that the odd prime $p$ ($2<p\le 10^{18}$) in each test case is fixed before the interaction starts, and will not change with your input.

If your final output is correct, you will get $\text{Accepted}$.

If your $m$ or $a_i$ do not satisfy the constraints, or your final output is incorrect, you will get $\text{Wrong Answer}$.

In addition, other verdicts will still be returned during judging according to the usual situations.

2
3 1

3

9

9


3 2

4

4

4

1

2

3

100
3 9 27

1

7

49

49
0 0 0

Hint

In the first test case, the odd prime $p=3$ in MCPlayer542's hand, so $q=p^k=3$.

We choose the array $a=\{1,\ 2,\ 3\}$, and obtain $g(3^1)=3, \ g(3^2)=9, \ g(3^3)=9$ in order.

Then we guess $p=3$ and choose $m=100$, so we output $3^1\bmod (100\times 1)=3, \ 3^2\bmod (100\times 2)=9, \ 3^3\bmod (100\times 3)=27$.

In the second test case, the odd prime $p=7$ in MCPlayer542's hand, so $q=p^k=49$.

We choose the array $a=\{1,\ 7,\ 49\}$, and obtain $g(49^1)=4,\ g(49^7)=4,\ g(49^{49})=4$ in order.

Then we keenly notice $p=7$ and choose $m=49$, so we output $49^1\bmod (49\times 1)=0, \ 49^7\bmod (49\times 7)=0, \ 49^{49}\bmod (49\times 49)=0$.

Note: The phrase “keenly notice” in the second test case is only used as an illustration of the interactive process, and does not guarantee that the above interaction can determine that $p=7$.

Translated by ChatGPT 5