I. Prime Guess I
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

MCPlayer542 has a mysterious odd prime number $$$p$$$, but he doesn't want to let you know its value.

He plans to encrypt the number with a function $$$f(x)$$$ whose value is the sum of digits of $$$x$$$ in decimal, e.g.$$$f(5)=5$$$, $$$f(542)=5+4+2=11$$$, $$$f(1024)=1+0+2+4=7$$$.

However, considering you're so smart, he decides to change the function to the following one after a moment's thought: $$$$$$g(x)=f(f(f(f(f(f(f(f(f(f(x))))))))))$$$$$$ That is, apply $$$10$$$ times $$$f(x)$$$ in a row. To make the matter worse, he replaces $$$p$$$ with $$$q=p^k$$$ as well.

Now he is going to give you $$$n$$$ integers $$$g(q^{a_1}),\ g(q^{a_2}),\ \ldots,\ g(q^{a_n})$$$ and he requires the value of $$$$$$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)$$$$$$ respectively.

He's sure that you'll never make a successful guess, so he doesn't mind if you choose $$$m$$$ and $$$a_1,\ a_2,\ \ldots,\ a_n$$$ yourself. Can you accomplish this task?

Please note that there are restrictions on the range of $$$m$$$.

Input

Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$($$$1\le t\le 500$$$) — the number of test cases. The description of the test cases follows.

Interaction

The first line of each test case contains two integers $$$n$$$ and $$$k$$$($$$1\le n\le 50,\ 1\le k\le 10^9$$$), separated by a single space.

For each interaction following, output a single integer $$$a_i$$$($$$1\le a_i\le 10^{18}$$$, $$$a_i$$$ should be pairwise distinct) — the power of $$$q$$$ in a query.

After each query, you should read a single integer, $$$g(q^{a_i})$$$.

After $$$n$$$ rounds of interaction, you are required to output a single integer $$$m$$$($$$m\ge 35$$$, $$$1\le m\cdot a_i\le 10^{18}$$$) in a line, and $$$n$$$ integers separated by single spaces in the following 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)$$$.

You must make exactly $$$n$$$ queries, then output the answer and terminate your program, otherwise you may get unpredictable verdicts.

Please note that after each round of your output(i.e. after outputting $$$a_i$$$ in each query and after outputting $$$m$$$ and answers finally) it is required to output the end of line and flush the output. Otherwise, you will get the verdict Idleness Limit Exceeded. To do this, use:

  • fflush(stdout) in C;
  • cout.flush() in C++;
  • System.out.flush() in Java;
  • stdout.flush() in Python.

It is guaranteed that the odd prime number $$$p$$$($$$2 \lt p\le 10^{18}$$$) is fixed and does not change during the interaction.

Scoring

If the answer in your final output is correct, you will get the verdict Accepted;

If $$$m$$$ or $$$a_i$$$ in your output does not meet the restrictions, or your answer is incorrect, you will get the verdict Wrong Answer.

You may also get other verdicts if their usual cases occur.

Example
Input
2
3 1

3

9

9


3 2

4

4

4
Output


1

2

3

100
3 9 27

1

7

49

49
0 0 0
Note

In the first test case, $$$p=3$$$, so we have $$$q=p^k=3$$$.

We may choose $$$a=\{1,\ 2,\ 3\}$$$, then we receive $$$g(3^1)=3,\ g(3^2)=9,\ g(3^3)=9$$$, respectively.

Then we find that $$$p=3$$$. By choosing $$$m=100$$$, we should 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, $$$p=7$$$, so we have $$$q=p^k=49$$$.

We may choose $$$a=\{1,\ 7,\ 49\}$$$, then we receive $$$g(49^1)=4,\ g(49^7)=4,\ g(49^{49})=4$$$, respectively.

Then we may guess $$$p=7$$$. By choosing $$$m=49$$$, we should output $$$49^1\bmod (49\times 1)=0,\ 49^7\bmod (49\times 7)=0,\ 49^{49}\bmod (49\times 49)=0$$$.

Please note that the explanation of the second test case is only intended to be an example of the interaction, it is not guaranteed that the interaction above will determine $$$p=7$$$.