Problem 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.

Input

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

Each test case contains two lines.

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

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

Output

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

1
6
1 2 4 8 16 32

10