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 c1⋅a1+c2⋅a2+…+ck⋅ak where c1,c2,…,ck are integers (which may be zero, positive, or negative).
The first line contains an integer t (1≤t≤100), the number of test cases.
The first line of each test case contains an integer n (1≤n≤105), the size of the set. The second line contains n distinct integers a1,a2,…,an (1≤ai≤105).
The sum of n over all test cases does not exceed 3⋅106.
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.
352 4 6 8 10512 15 21 30 3532 3 6
2 4 6 3 35 21 30 2 2 3
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⋅2+(−2)⋅3, which is an integer linear combination of {2,3}.
Name |
---|