I tried to solve this problem with the help of bitmask. Because the number of prime is very low. But couldn't come up with a exact solution. It will be helpful if anyone help me to find out a solution. The problem statement is given below:

You are given N(1<=N<=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.

Input:

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

Output:

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

Sample Input:

1

3

2 1 6

Sample Output

8