An array of integers is called good if all its elements are perfect squares.

You are given an array A of N integers. In one move, you can do the following:
Pick a subset of indices of the array, say ${i_{1}, i_{2}, \ldots, i_{k}$} where 1 ≤$i_{1} < i_{2} < \ldots < i_{k}$ ≤ N
Next, pick an integer X > 0
Finally, multiply the value at each chosen index by X, i.e, set A_{i_{j}} to $A_{i_{j}} \cdot X$ for each 1 ≤ j ≤ k

Find the minimum number of moves required to make the array good.

Note: The value of X is fixed for a given move, but can vary between moves.

------ Input Format ------

• The first line of input contains an integer T, denoting the number of test cases. The description of T test cases follows.
• Each test case contains two lines of input.
• The first line of each test case contains N, the size of the array.
• The second line contains $N space-separated integers A_{1}, A_{2}, \ldots, A_{N}$.

------ Output Format ------

For each testcase, output in a single line the minimum number of moves required to make the array good.

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{4}$
$1 ≤ A_{i} ≤ 10^{8}$
- The sum of $N$ across all testcases won't exceed $10^{4}$.

------ subtasks ------

Subtask #1 (100 points): Original constraints

----- Sample Input 1 ------
5
3
15 2 4
4
15 14 4 9
3
10 3 6
2
4 9
2
2 8

----- Sample Output 1 ------
2
2
3
0
1

----- explanation 1 ------
Test case $1$: One possible sequence of moves is:
- Multiply the first element by $15$
- Multiply the second element by $2$

The array is now $[225, 4, 4] = [15^{2}, 2^{2}, 2^{2}]$, which is good.

Test case $3$: One possible sequence of moves is:
- Multiply the first and third elements by $8$
- Multiply the second and third elements by $3$
- Multiply the first element by $20$

The array is now $[1600, 9, 144] = [40^{2}, 3^{2}, 12^{2}]$, which is good.

Test case $4$: The array is already good, since $[4, 9] = [2^{2}, 3^{2}]$, so no moves need to be made.

见题面

见题面