G. Send GCDs

Source: Codeforces 2237G
Contest: Order Capital Round 2 (Codeforces Round 1104, Div. 1 + Div. 2)
Time limit: 3 seconds
Memory limit: 256 megabytes

Statement

This is a run-twice (communication) interactive problem.

There are two players: Ja the Ghost and Quack the Duck. The jury (otherwise known as the interactor of this problem) will first interact with Ja. After Ja ends the interaction, the jury will interact with Quack. Note that Ja and Quack may not directly pass information to each other; both players are only able to send information to or receive information from the jury.

Before the interaction, the jury determines an integer $n$ and an array of $n$ positive integers $a_1, a_2, \ldots, a_n$. These values are consistent across both players.

Ja receives $n$ and an array of $n$ positive integers $a_1, a_2, \ldots, a_n$ from the jury, which he wants to send to Quack, where $a_i \le 10^6$. To do this, Ja will select an integer $k$, where $$k \le \left\lceil \frac{10n}{9} \right\rceil + 150,$$ and create an array of positive integers $b_1, b_2, \ldots, b_k$, where $b_i \le 10^6$, and send it back to the jury. Then the jury will give Quack the integers $n$ and $k$. Quack can ask the jury at most $180n + 150$ queries in the following form:

• Choose any two integers $i$ and $j$ ($1 \le i, j \le k$, $i \neq j$), and the jury will respond with $\mathrm{gcd}(b_i, b_j)$.

Here, $\gcd(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$.

Note that both $a$ and $b$ are hidden from Quack; Quack can only get information from queries.

Ja wants to ensure that Quack can determine the original array $a$. Your task is to act as both players and determine an optimal interaction strategy for both players so that Quack determines the original array $a$ correctly.

First Run

Your code will run exactly twice on each test. On the first run, you will be Ja.

Input

The first line of the input contains the string first. The purpose of this is so your program recognizes that this is its first run, and it should act as Ja.

The second line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first line of the $i$-th test case contains an integer $n$ ($1 \le n \le 10^3$) — the length of $a$ for the $i$-th test case.

The second line of the $i$-th test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^6$) — the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^3$.

Output

For each test case, first print an integer $k$ ($1 \le k \le \left\lceil \frac{10n}{9} \right\rceil + 150$), denoting the length of the array $b$. Then print $k$ integers $b_1, b_2, \ldots, b_k$ ($1 \le b_i \le 10^6$), denoting the array $b$ that Ja will send to the jury. This array will be used to answer the queries in the second run.

After this, proceed to the next test case or terminate your program if it was the last test case.

Second Run

On the second run, you are Quack.

Input

The first line of the input contains the string second. The purpose of this is so your program recognizes that this is its second run, and it should act as Quack.

The second line of the input contains exactly one integer $t$ ($1 \le t \le 100$) — the number of test cases. Note that this number is equal to $t$ from the first run input.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 10^3$, $1 \le k \le \left\lceil \frac{10n}{9} \right\rceil + 150$). This denotes the lengths of $a$ and $b$, respectively.

Note that the test cases in the second run may be shuffled. Please see the example test case for further illustration.

Interaction

For the $i$-th test case, recall that you will first receive $n$ and $k$ in the input from the jury according to the input format above. After receiving those inputs, you will be able to make at most $180n + 150$ queries of the following form:

• ? i j ($1 \leq i, j \leq k$, $i \neq j$).

After each query, the jury will respond with $\mathrm{gcd}(b_i, b_j)$, which you should read through the input stream.

If your program makes more than $180n + 150$ queries, your program should immediately terminate and receive the verdict Wrong Answer. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

Once you are ready to report the original array $a$, you may do so in the following format:

• ! $a_1, a_2, \ldots ,a_n$ ($1 \leq a_i \leq 10^6$).

Then, you will either proceed to the next test case, or your program must terminate if you have processed every test case.

The interactor is not adaptive. That is, both arrays $a$ and $b$ will not change during the interaction and will always be the same arrays as in the first run.

After printing each query do not forget to output the end of line and flush$^{\text{∗}}$ the output. Otherwise, you will get Idleness limit exceeded verdict.

If, at any interaction step, you read $-1$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

$^{\text{∗}}$To flush, use:

• fflush(stdout) or cout.flush() in C++;
• sys.stdout.flush() in Python;
• see the documentation for other languages.

Input

Output

Note

In the first run, there are two test cases.

For the first test case, Ja is given $a = [1, 1, 4, 5, 1, 4]$. He decides to send $b = [20, 1, 1, 4, 5, 1, 4]$.

For the second test case, Ja is given $a = [2, 6, 10]$. He decides to send $b = [30, 2, 6, 10]$.

In the second run, the order of the test cases is shuffled. Therefore, Quack first receives the test case with $n = 3$ and $k = 4$. He asks $\mathrm{gcd}(b_1, b_i)$ for $i = 2, 3, 4$, and the jury answers $2, 6, 10$. Thus, Quack can determine that the original array is $[2, 6, 10]$.

Then Quack receives the test case with $n = 6$ and $k = 7$. He asks $\mathrm{gcd}(b_1, b_i)$ for $i = 2, 3, 4, 5, 6, 7$, and the jury answers $1, 1, 4, 5, 1, 4$. Thus, Quack can determine that the original array is $[1, 1, 4, 5, 1, 4]$.

This example illustrates that although the test cases in the second run may appear in a different order, the same arrays $a$ and $b$ from the first run are used.

Examples

first
2
6
1 1 4 5 1 4
3
2 6 10

7
20 1 1 4 5 1 4
4
30 2 6 10

second
2
3 4

2

6

10
6 7

1

1

4

5

1

4

? 1 2

? 1 3

? 1 4

! 2 6 10

? 1 2

? 1 3

? 1 4

? 1 5

? 1 6

? 1 7

! 1 1 4 5 1 4