RLPRIMES - RELATIVE PRIMES

You are given a set numbers. Output the number of pairs of relatively prime numbers found in the set.

Input

The first line consists of an integer t, the number of test cases. (1 <= t <= 100).

For each test case:

The first line contains the size of the set, N (1 < N <= 100).

The next line contains N space separated integers each of which is in the range [1, 100].

Output

For each test case, output the number of pairs of relatively prime numbers found in the set.

Example

Input:
2
5
1 2 3 4 5 
2
1 1

Output:
9
1

Added by:cegprakash
Date:2013-01-20
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF

hide comments
2013-05-24 00:18:10 Carlos Matos
is there a time limit?

reply: yes. 2 seconds!

Last edit: 2014-01-22 08:30:44
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.