H. Rayan vs. Rayaneh
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Rayan makes his final efforts to win Reyhaneh's heart by claiming he is stronger than Rayaneh (i.e., computer in Persian). To test this, Reyhaneh asks Khwarizmi for help. Khwarizmi explains that a set is integer linearly independent if no element in the set can be written as an integer linear combination of the others. Rayan is given a set of integers each time and must identify one of the largest possible integer linearly independent subsets.

Note that a single element is always considered an integer linearly independent subset.

An integer linearly combination of $$$a_1, \ldots, a_k$$$ is any sum of the form $$$c_1 \cdot a_1 + c_2 \cdot a_2 + \ldots + c_k \cdot a_k$$$ where $$$c_1, c_2, \ldots, c_k$$$ are integers (which may be zero, positive, or negative).

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$), the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$), the size of the set. The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$).

The sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^6$$$.

Output

In the first line of each test case print the size of the largest integer linearly independent subset.

In the next line, print one such subset in any order. If there are multiple valid subsets, print any one of them.

Example
Input
3
5
2 4 6 8 10
5
12 15 21 30 35
3
2 3 6
Output
2
4 6
3
35 21 30
2
2 3
Note

In example 1, $$$\{4, 6\}$$$ is an integer linearly independent subset. It can be proven that there is no integer linearly independent subset with at least $$$3$$$ elements.

In example 2, $$$\{35, 21, 30\}$$$ is an integer linearly independent subset because no integer linear combination of any two elements can create the third. There is no integer linearly independent subset with at least $$$4$$$ elements.

In example 3, $$$\{2, 3, 6\}$$$ is not an integer linearly independent subset since $$$6$$$ can be written as $$$6 \cdot 2 + (-2) \cdot 3$$$, which is an integer linear combination of $$$\{2, 3\}$$$.