NGCD - NO GCD

no tags 

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


hide comments
:D: 2018-10-23 01:06:16

Very good problem. It's not really about factorization and underlying problem is fairly difficult. It's also properly described, but I will still sum up answers to question in the comments:

Re jarnura: Square free - not divisible by any square of an integer. 2 is square free (divisors 1 and 2). 100 is not square free (divisible by 25=5*5), as well as 27 (divisible by 9=3*3).

Re ashish kumar: Description correctly specifies the integer limit for input numbers. Just read first paragraph carefully.

Re jinxer: Answer for "1\n 2\n 1 1" is 4 because bcd(1,1)=1 so all possible pairs should be counter: (1,1) (1,2), (2,1), (2,2)

waffl3: 2016-12-06 14:15:17

getting tle -_-
...
...
i don't know
Euclidean algorithm, maybe
btw. please help \(0_0)/

Last edit: 2016-12-06 14:19:32
jinxer: 2016-06-12 16:15:24

getting TLE..any hint ???
and how is the output is 4 for the
INPUT:
1
2
1 1

ashish kumar: 2016-05-05 05:36:49

What is the range of integer ???

jarnura: 2016-04-27 14:41:39

2 is a square free number or not?

Samuel Nacache: 2016-04-27 04:43:46

@lumaere yes, it's the product of all the primes less than 50

lumaere: 2016-04-17 01:59:55

Is there an upperbound on the size of each number?

vivekrnj: 2016-04-07 19:48:26

me getting TLE..hint!

Emruz Hossain: 2016-04-05 19:08:02

@rainy Jain: Output of your test case is 89

rainy jain : 2016-04-05 04:53:41

What will be the output in this case:
1
10
1 2 3 33 77 51 2 77 77 1


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