Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.

Chef is teaching his students about properties of integers. Today he is teaching them about numbers which are squares of some number, e.g. 1, 4, 9, 16, 25 etc. These numbers are said perfect squares.

He gave his students the following task as homework. He gives an array a consisting of n positive integers. He calls the array w0w if for every pair of indices i, j, the product a_{i} * a_{j} is a perfect square.

Chef wants you to make this array w0w. For achieving this, you can pick any integer a_{i} and can multiply it by any prime number. You can perform this operation several times, even multiple times on the same number. Find out the minimum number of operations that you will require.

------ Input ------

The first line of the input contains an integer T denoting the number of the test cases.
The first line of each test case will contain an integer n denoting number of elements in array a.
The next line will contain n space separated integers denoting elements of array a.

------ Output ------

For each test case, output a single integer corresponding to minimum number of operations required to make array w0w.

------ Constraints ------

1 ≤ T, n, a_{i} ≤ 10^{6}
1 ≤ Sum of n over all test cases in a single test file ≤ 10^{6}

------ Subtasks ------

Subtask #1: (10 points)

1 ≤ T, n, a_{i} ≤ 10^{5}
a_{i} is prime.
1 ≤ Sum of n over all test cases in a single test file ≤ 10^{5}

Subtask #2: (20 points)

1 ≤ T, n, a_{i} ≤ 10^{6}
a_{i} is prime.
1 ≤ Sum of n over all test cases in a single test file ≤ 10^{6}

Subtask #3: (30 points)

1 ≤ T, n, a_{i} ≤ 10^{5}
1 ≤ Sum of n over all test cases in a single test file ≤ 10^{5}

Subtask #4: (40 points)

Original Constraints

----- Sample Input 1 ------
3

3

2 2 2

3

1 2 2

3

2 4 6
----- Sample Output 1 ------
0

1

2
----- explanation 1 ------
Example case 1. If you multiply any pair of integers in the array, the product is 4, which is square. So, the array is w0w already.
Example case 2. You can multiply the first number by 2, then the array will become w0w. So the minimum number of operations required will be 1.

见题面

见题面