Count GCD Pairs

You are given several test cases. For each test case, you are provided with an array of positive integers. Your task is to count the number of pairs \((i, j)\) (with \(i < j\)) such that the greatest common divisor (GCD) of \(a_i\) and \(a_j\) is greater than 1.

Input Format: The first line of input contains an integer \(T\), the number of test cases. Each test case consists of two lines: the first line contains an integer \(n\), the number of elements in the array, and the second line contains \(n\) space-separated positive integers.

Output Format: For each test case, output a single line containing the number of pairs \((i, j)\) for which \(\gcd(a_i, a_j) > 1\).

Note: Use standard input and output for reading and writing data.

inputFormat

The input begins with a single integer \(T\) representing the number of test cases. Each test case is described below:

• The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), the number of elements in the array.
• The second line contains \(n\) space-separated positive integers \(a_1, a_2, \dots, a_n\).

outputFormat

For each test case, output a single integer on a separate line: the number of pairs \((i, j)\) (with \(i 1\).

## sample

2
3
6 10 15
4
12 15 18 20

3
6

</p>