Description

Now Mr.I has an array a consisting of n integers.

He now wants to know how many triples $(i,j,k)$ satisfy $i < j < k$ and $a_i∗a_j∗a_k$ is a square number .

The definition of a square number is a number that can be expressed as the product of two identical integers.

For example, 1, 4, 9, 16, 25, and 36 are square numbers, but 2, 3, and 6 are not.

Format

Input

The first line contains an integer T$(T \leqslant 6)$ . Then T test cases follow.

Each test case contains two lines.

The first one contains an integer n $(1 \leqslant n \leqslant 10^5)$ — length of the array a.

The second one contains n integers $a_1,a_2,...,a_n$ $(1 \leqslant a_i \leqslant 10^5)$

Output

For each test case, output a single line containing a single integer — the number of triples that meet the conditions.

Samples

1
6
1 2 4 8 16 32

10