Largest GCD Subset

You are given T test cases. For each test case, you are given an array of N positive integers. Your task is to find the size of the largest subset of elements such that the greatest common divisor (GCD) of all elements in that subset is greater than 1.

If there is no subset with a GCD greater than 1, output 0. Note that a subset is defined as any collection of elements from the array (possibly the entire array) and the GCD of a single number is the number itself.

Hint: Iterate over all possible divisors starting from 2 up to the maximum value in the array. For each divisor g, count how many numbers in the array are divisible by g. The answer is the maximum count obtained for any such divisor.

The mathematical representation of the problem is as follows:

$$\text{Find } \max_{g \ge 2}\; \Bigl\{ \text{count}(g) : \text{where } \text{count}(g)=\#\{a_i \in arr : g \mid a_i\} \Bigr\}. $$

inputFormat

The first line of input contains an integer T, representing the number of test cases.
For each test case, the first line contains an integer N, the size of the array, and the second line contains N space-separated positive integers.

Example:

2
5
2 4 6 8 10
4
5 10 15 20

outputFormat

For each test case, output a single line which contains an integer representing the size of the largest subset where the GCD of the subset is greater than 1.

Example:

5
4

## sample

1
5
2 4 6 8 10

5

</p>