SP26778 NGCD - NO GCD

You are given $N$ ($1\le N\le 100000$) integers. Each integer is square free (meaning it has no divisor which is a square number except 1) and all the prime factors are less than 50. You have to find out the number of pairs are there such that their GCD is 1 or a prime number. Note that $(i, j)$ and $(j, i)$ are different pairs if $i$ and $j$ are different.

The first line contains an integer $T$ ($1\le T\le 10$), the number of tests. Then $T$ tests follows. First line of each tests contain an integer $N$. The next line follows $N$ integers.

Print $T$ lines. In each line print the required result.

- $\gcd(1, 2) = 1$. - $\gcd(2, 1) = 1$. - $\gcd(2, 6) = 2$, a prime number. - $\gcd(6, 2) = 2$, a prime number. - $\gcd(1, 6) = 1$. - $\gcd(6, 1) = 1$. - $\gcd(2, 2) = 2$, a prime number. - $\gcd(1, 1) = 1$. So, total of 8 pairs. *Problem Setter: Nafis Sadique, Jahangirnagar University*.