E. Game of Divisors
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Rami and Khalil are fierce competitors in two-player games. This time, they agreed to play the following turn-based game, designed by Khalil.

The game starts with a list of $$$n$$$ positive integers $$$A = [A_1, A_2, \dots, A_n]$$$.

On each turn, the current player selects one number $$$A_i$$$ from the list and replaces it with either:

  • A proper divisor of $$$A_i$$$ (a positive divisor less than $$$A_i$$$ itself), or
  • Any positive integer whose number of distinct prime factors is strictly less than that of $$$A_i$$$.

The player who cannot make a move on their turn loses. Khalil will be the starting player.

While Khalil was carefully considering his first move, Rami realised something interesting: he can sneakily add some positive integers to the list before the game starts to guarantee his win (as the second player).

Since Rami wants to avoid suspicion, he needs to minimize the number of integers he adds. If multiple minimal solutions exist, any valid set will work.

Help Rami determine the smallest set of positive integers (possibly empty) that he can add to the list so that he will win assuming both players play optimally.

Input
  • The first line contains an integer $$$1\le T\le 10^4$$$, denoting the number of test cases
  • The first line of the $$$i^\text{th}$$$ test case contains an integer $$$0 \le n \le 10^6,$$$ denoting the size of the array $$$A$$$
  • The second line of the $$$i^\text{th}$$$ test case contains $$$n$$$ integers $$$1 \le A_1,\dots,A_n \le 10^6$$$

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6.$$$ Formally: $$$\sum_{i}n_i \le 10^6$$$

Output

For each test case, output a line containing:

  • First an integer $$$0 \le m\le 10^6,$$$ denoting the number of added integers.
  • Then, if $$$m \neq 0$$$, output $$$m$$$ integers $$$1 \le B_1, \dots, B_m \le 10^6$$$, denoting the numbers that were added.
Example
Input
2
2
9 27
5
2 3 6 5 7
Output
1 3
1 35
Note

After Rami adds these integers, the game proceeds with Khalil making the first move on the modified list $$$A'=\mathrm{concat}(A,B)=[A_1,\dots,A_n, B_1,\dots,B_m]$$$