Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

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 a1,,ak is any sum of the form c1a1+c2a2++ckak where c1,c2,,ck are integers (which may be zero, positive, or negative).

Input

The first line contains an integer t (1t100), the number of test cases.

The first line of each test case contains an integer n (1n105), the size of the set. The second line contains n distinct integers a1,a2,,an (1ai105).

The sum of n over all test cases does not exceed 3106.

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 62+(2)3, which is an integer linear combination of {2,3}.