J :: Julia Composite Subset

Time Limit: 10 Seconds Memory Limit: 32768 KB

Julia is a teacher and wants to teach her students how to compute greatest-common-divisor (gcd) of two integers. Hence, she desires to have a good subset as a set of integers, none of which are relatively prime (e.g. {12, 15, 18, 20, 30}). She starts from S as a candidate set of positive integers. Then for each sequence <x=y₁, y₂, ..., y_2k+1> (k>0), the number x₁ is thrown out if following conditions are held:

y_i and y_i+1 are relatively prime
x and y_2k+1 are also relatively prime
x is smaller than all y_i>1

In other words, from each odd size cycle of integers, in which the adjacent ones are relatively prime, the smallest one is thrown out. This process is continued until there is no such sequence. This filtering is done from the largest x to the smallest one. For S={1, 2, 3, 4, 5, 12, 15, 18, 20, 30}, considering the sequences <3,4,5> and <1,2,5>, in order, leads to removing 3 and 1, respectively.

The good subset is then chosen from the remained numbers. Given S, find the maximum possible good subset after the filtering. For the above example, from the set of remained numbers, {2, 4, 12, 18, 20, 30} can be extracted as the largest good subset.

Input

In the first line, an integer T<20 is given as the number of test cases. Each test case is represented by a line containing a positive integer n≤1000 as the size of S followed by a line containing n integers as the members of S.

Output

For each test case, output two separated integers A and B in a line, whereas A is the size of the set after initial filtering and B is the maximum size of a good subset can be finally extracted.

Sample Input

3
10
1 2 3 4 5 12 15 18 20 30
4
12 14 15 20
6
12 14 15 20 23 29

Sample Output

8 6
4 3
2 1

Submit

Source: 12th Iran Nationwide Internet Contest IV