Perfect Square Pairs

You are given an array of n positive integers. Your task is to count the number of distinct pairs (i, j) such that \(1 \le i < j \le n\) and the product \(A[i] \times A[j]\) is a perfect square. A perfect square is an integer that can be written in the form \(k^2\), where \(k\) is an integer.

For example, consider the array [1, 4, 7, 9]. The valid pairs are:

• (1, 2): \(1 \times 4 = 4 = 2^2\)
• (1, 4): \(1 \times 9 = 9 = 3^2\)
• (2, 4): \(4 \times 9 = 36 = 6^2\)

Thus, the answer is 3.

inputFormat

The first line contains a single integer \(T\) denoting the number of test cases. For each test case, the first line contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated positive integers.

outputFormat

For each test case, output a single line containing the number of pairs \((i, j)\) such that the product \(A[i] \times A[j]\) is a perfect square.

## sample

1
4
1 4 7 9

3

</p>