Read problem statements in [Russian], [Mandarin Chinese], [Bengali], and [Vietnamese] as well.

Let's define a function F(X) as follows:

$F(X) = \frac{X}{Y}$

where Y is the largest perfect square that divides X.

For example,
The largest perfect square that divides 12 is 4. Hence $F(12) = \frac{12}{4} = 3$.
The largest perfect square that divides 36 is $36. Hence F(36) = \frac{36}{36} = 1$.
The largest perfect square that divides 7 is 1. Hence $F(7) = \frac{7}{1} = 7$.

You are given an array A consisting of N integers. A pair of integer (i, j) is called Good if 1 ≤ i < j ≤ N and F(A_{i} * A_{j}) > 1. Find the number of Good pairs.

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

• The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains an integer N.
• The second line of each testcase contains $N space-separated integers A_{1}, A_{2}, \dots , A_{N}$.

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

For each test case, print a single line containing one integer - the number of Good pairs.

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{6}$
- The sum of $N$ over all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------
3
3
2 3 12
4
1 2 3 4
3
2 3 7
----- Sample Output 1 ------
2
5
3
----- explanation 1 ------
Test case $1$:
- $(i = 1, j = 2)$: $F(A_{1} * A_{2}) = F(2 * 3) = F(6) = \frac{6}{1} = 6 > 1$.
- $(i = 1, j = 3)$: $F(A_{1} * A_{3}) = F(2 *12) = F(24) = \frac{24}{4} = 6 > 1$.
- $(i = 2, j = 3)$: $F(A_{2} * A_{3}) = F(3 *12) = F(36) = \frac{36}{36} = 1 \ngtr 1$.

So there are 2 Good pairs.

Test case $2$: All pairs except ($1, 4$) are Good pairs as $F(A_{1} * A_{4}) = F(1 * 4) = F(4) = \frac{4}{4} = 1 \ngtr 1$.

Test case $3$: All pairs are Good pairs.

见题面

见题面