NGCD - 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.

Example

Input:
1
3
2 1 6

Output:
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


Added by:Alim
Date:2016-04-01
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2016-04-02 04:45:01 [Rampage] Blue.Mary
Another sample:
Input:
1
2
1 1

Output:
4
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.