Largest GCD Subset

You are given several test cases. In each test case, you are provided an array of n positive integers. Your task is to select a subset of the array (possibly the entire array) such that the greatest common divisor (GCD) of all the numbers in the selected subset is greater than 1.

The answer for each test case is the maximum size of a subset satisfying this condition. If no subset of size at least 2 has a GCD greater than 1, then output 1 (since any single number is considered as a valid subset).

Note: It is assumed that any integer greater than 1 has at least one prime divisor. Use prime factorization to determine common factors among numbers.

Mathematical formulation:

Given an array \(a_1, a_2, \ldots, a_n\), find the maximum \(k\) such that there exists indices \(i_1, i_2, \ldots, i_k\) satisfying \[ \gcd(a_{i_1}, a_{i_2}, \ldots, a_{i_k}) > 1. \]

inputFormat

The input is read from standard input and has the following format:

T
n
a1 a2 ... an
n
a1 a2 ... an
... (T test cases)

Here, T is the number of test cases. For each test case, the first line contains an integer n denoting the number of integers in the test case, and the second line contains n space-separated positive integers.

outputFormat

For each test case, output the maximum size of a subset (each on a new line) such that the GCD of the subset is greater than 1. The output should be printed to standard output.

## sample

2
5
10 15 20 25 30
4
3 6 9 12

5
4

</p>