Limits 1.5s, 512 MB

You are given N integers. Each integer is square free (i.e. 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 these numbers 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 ≤ T ≤ 10), the number of tests. Then T test cases follow.

The first line of each test cases contains an integer N (1 ≤ N ≤ 100000). The next line contains N integers.


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


2 1 6

In the sample case, the following pairs satisfy the criteria:

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

This problem was authored for CodeMask Championship 2016 and is being hosted on Toph per organizer’s request.


Login to submit.


48% Solution Ratio
sgtlaughEarliest, May '16
Kuddus.6068Fastest, 0.2s
sgtlaughLightest, 393 kB
RakibJoyShortest, 1082B
Toph uses cookies. By continuing you agree to our Cookie Policy.