spoj#NGCD. NO GCD

NO GCD

 

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 Sample Output
1
3
2 1 6 8
Explanation
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: Md Abdul Alim, CEO & Founder at CodeMask

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

Sample Output

1

3

2 1 6 

8 

 

Explanation

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