You are given an array A of length N. 

A pair (i, j) (1≤ i< j ≤ N) is said to be *good* if gcd(A_{i}, A_{j}) = lcm(A_{i}, A_{j}). Here gcd denotes the [greatest common divisor] and lcm denotes [least common multiple].

Find the total number of *good* pairs present in the given array.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first line of each test case contains an integer N - the length of the array A.
- The second line of each test case contains N space-separated integers A_{1},A_{2},\ldots,A_{N}.

------ Output Format ------ 

For each test case, output on a new line the total number of such *good* pairs possible in the given array.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $3 \cdot 10^{5}$.

----- Sample Input 1 ------ 
5
2
5 9
5
1 5 5 5 9
8
2 5 5 2 9 9 9 12
4
12 12 18 18
5
12 15 10 5 9

----- Sample Output 1 ------ 
0
3
5
2
0
----- explanation 1 ------ 
Test case $1$: No *good* pair is present.

Test case $2$: The *good* pairs $(i, j)$ are: $(2, 3), (3, 4),$ and $(2, 4)$. To elaborate, $gcd(A_{2}, A_{3}) = lcm(A_{2}, A_{3}) = 5$.

Test case $3$: The *good* pairs $(i, j)$ are: $(1, 4), (2, 3), (5, 6), (6, 7),$ and $(5, 7)$. To elaborate, $gcd(A_{1}, A_{4}) = lcm(A_{1}, A_{4}) = 2$.

Test case $4$: The *good* pair $(i, j)$ are: $(1, 2),$ and $(3, 4)$. To elaborate, $gcd(A_{3}, A_{4}) = lcm(A_{3}, A_{4}) = 18$.

Test case $5$: No *good* pair is present.

Source: codechef | Difficulty: EASY
Tags: Sorting

Data structures

Mathematics


Solutions:
for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	lis.sort()
	ans = 0
	cou = 1
	for i in range(1, n):
		if lis[i] == lis[i - 1]:
			cou += 1
		else:
			ans = ans + cou * (cou - 1) / 2
			cou = 1
	ans = ans + cou * (cou - 1) // 2
	print(int(ans))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	y = list(set(l))
	s = 0
	if len(y) == n:
		s = 0
	else:
		for i in range(len(y)):
			x = l.count(y[i])
			s = s + x * (x - 1) // 2
	print(int(s))


for _ in range(int(input())):
	num = int(input())
	AA = list(map(int, input().split()))
	f = {}
	for i in AA:
		if i in f:
			f[i] += 1
		else:
			f[i] = 1
	ps = 0
	for j in f.values():
		ps += j * (j - 1) // 2
	print(ps)


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	freq = {}
	for a in A:
		if a in freq:
			freq[a] += 1
		else:
			freq[a] = 1
	pairs = 0
	for n in freq.values():
		pairs += n * (n - 1) // 2
	print(pairs)


from math import comb
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = Counter(a)
	ans = 0
	for num in c:
		ans += comb(c[num], 2)
	print(ans)


from collections import Counter
import math
for i in range(int(input())):
	n = int(input())
	r = 0
	l = list(map(int, input().split()))
	c = Counter(l)
	for i in c:
		r = r + math.comb(c[i], 2)
	print(r)


def gcd(n1, n2):
	n = min(n1, n2)
	cd = 1
	for i in range(2, n + 1):
		if n1 % i == 0 and n2 % i == 0:
			cd = i
	return cd

def lcm(n1, n2):
	return abs(n1 * n2) / gcd(n1, n2)
t = int(input())
for k in range(t):
	n = int(input())
	A = [int(x) for x in input().split()]
	cc = 0
	c = 0
	num = 0
	prev = 0
	cur = 0
	A.sort()
	for i in range(1, len(A)):
		prev = i - 1
		cur = i
		if A[cur] == A[prev]:
			c += 1
		else:
			cc += (c + 1) * c // 2
			c = 0
	cc += (c + 1) * c // 2
	c = 0
	print(cc)


import collections
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = dict(collections.Counter(l))
	d = 0
	for i in k:
		if k[i] > 1:
			n = k[i]
			p = n * (n - 1) // 2
			d = d + p
	print(d)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	ans = 0
	for i in d:
		if d[i] == 1:
			ans += 0
		else:
			ans += d[i] * (d[i] - 1) // 2
	print(ans)


import math
from collections import Counter
t = int(input())
for tc in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	c = Counter(l)
	p = 0
	for j in c:
		p += math.comb(c[j], 2)
	print(p)


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(c) for c in input().split()]

	def fac(n):
		if n == 0:
			return 0
		else:
			ans = 0
			for i in range(1, n):
				ans = ans + i
			return ans
	b = {}
	for j in range(n):
		if a[j] not in b:
			b.update({a[j]: 1})
		else:
			k = b[a[j]] + 1
			b.update({a[j]: k})
	l = 0
	for k in b:
		l = l + fac(b[k])
	print(l)


for _ in range(int(input())):
	N = int(input())
	A = [int(i) for i in input().split()]
	countADict = {}
	for num in A:
		countADict[num] = countADict.get(num, 0) + 1
	count = 0
	for num in countADict:
		if countADict[num] > 1:
			count += int(countADict[num] * (countADict[num] - 1) / 2)
	print(count)


import math
for tc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	kmap = {}
	for ele in arr:
		if ele not in kmap:
			kmap[ele] = 1
		else:
			kmap[ele] += 1
	count = 0
	for key in kmap:
		count += math.comb(kmap[key], 2)
	print(count)


x = int(input())
rt = []
for nnm in range(0, x):
	ptr = int(input())
	op = str(input())
	hv = op.split(' ')
	gxz = []
	for iiy in hv:
		gxz.append(int(iiy))
	rt.append(gxz)
for eex in rt:
	pairs = 0
	dfrt = {}
	for mm in eex:
		if mm not in dfrt.keys():
			dfrt[mm] = 1
		else:
			fvxz = dfrt[mm]
			pairs += fvxz
			dfrt[mm] += 1
	print(pairs)


def solve(x):
	s = 0
	n = 1
	for i in range(x):
		s = s + n
		n = n + 1
	return s
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = 0
	d = {}
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for i in d:
		if d[i] > 1:
			s += solve(d[i] - 1)
	print(int(s))


from collections import Counter
import math
for _ in range(int(input())):
	n = int(input())
	a = Counter(map(int, input().split()))
	count = 0
	for value in a.values():
		if value > 1:
			count += math.comb(value, 2)
	print(count)


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	res = 0
	freq = {}
	for x in lis:
		if x in freq:
			freq[x] += 1
		else:
			freq[x] = 1
	for i in freq:
		res += freq[i] * (freq[i] - 1) / 2
	print(int(res))


t = int(input())
for i in range(t):
	input()
	s = list(map(int, input().split()))
	d = dict()
	maxi = 0
	for j in s:
		if not j in d:
			d[j] = 1
		else:
			d[j] += 1
		maxi = i
	res = 0
	for k in d:
		res += int((d[k] - 1) * d[k] / 2)
	print(res)


def count(n):
	return n * (n - 1) // 2
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	d = {}
	for i in a:
		d[i] = d.get(i, 0) + 1
	ans = 0
	for i in list(d.values()):
		ans += count(i)
	print(ans)


from math import comb
from collections import Counter
for k in range(int(input())):
	NU_MB = int(input())
	aarr = list(map(int, input().strip().split()))
	cout = Counter(aarr)
	answe = 0
	for j in cout:
		answe += comb(cout[j], 2)
	print(answe)


for _ in range(int(input())):
	t52 = int(input())
	d52 = {}
	l52 = [int(i52) for i52 in input().split()]
	for i52 in l52:
		d52[i52] = 0
	for i52 in l52:
		d52[i52] += 1
	sm = 0
	for i52 in d52:
		p52 = d52[i52]
		p52 -= 1
		p52 = (p52 + 1) * p52 // 2
		sm += p52
	print(sm)


import collections
from collections import Counter
for i in range(int(input())):
	count = 0
	n = int(input())
	arr = list(map(int, input().split()))
	dic = dict(Counter(arr))
	for k in dic.keys():
		if dic[k] != 1:
			val = dic[k]
			ad = val * (val + 1) // 2 - val
			count += ad
	print(count)


from math import comb
from collections import Counter
for _ in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	c = Counter(l)
	count = 0
	for i in c:
		count += comb(c[i], 2)
	print(count)


import os, sys, io, math
from re import *
from math import *
from array import *
from heapq import *
from bisect import *
from functools import *
from itertools import *
from statistics import *
from collections import *
I = lambda : [*map(int, sys.stdin.readline().split())]
IP = lambda : map(int, input().split())
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())

def f():
	(n, l) = (IN(), I())
	d = Counter(l)
	res = 0
	for i in d:
		res += comb(d[i], 2)
	return res
for _ in range(IN()):
	print(f())


import math
T = int(input())
for _ in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	count = 0
	curr = 0
	for i in range(1, n):
		if arr[i] == arr[i - 1]:
			curr += 1
		else:
			count += curr * (curr + 1) // 2
			curr = 0
	print(count + curr * (curr + 1) // 2)


from math import comb
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = Counter(a)
	res = 0
	for i in c:
		res += comb(c[i], 2)
	print(res)


from math import comb
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	dic = {}
	ans = 0
	for i in A:
		if i not in dic:
			dic[i] = 1
		else:
			dic[i] += 1
	for i in dic:
		ans += comb(dic[i], 2)
	print(ans)


from math import comb
for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	count = 0
	for i in d.keys():
		if d[i] > 1:
			count += comb(d[i], 2)
	print(count)


from collections import Counter
t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	C = Counter(l)
	count = 0
	for i in C:
		count = count + C[i] * (C[i] - 1) / 2
	print(int(count))


from collections import Counter
t = int(input())
for j in range(t):
	n = int(input())
	s = list(map(int, input('').split()))
	s = Counter(s)
	s = s.values()
	pairs = 0
	for val in s:
		if val > 1:
			pairs = pairs + val * (val - 1) / 2
	print(int(pairs))


T = int(input())
for i in range(T):
	N = int(input())
	(ans1, ans2) = (0, 0)
	L = list(map(int, input().split()))
	L.sort()
	for i in range(1, N):
		if L[i] == L[i - 1]:
			ans1 += 1
		else:
			if ans1 == 1:
				ans2 += 1
			elif ans1 > 1:
				ans2 = ans2 + ans1 + ans1 * (ans1 - 1) // 2
			ans1 = 0
	if ans1 == 0:
		print(ans2)
	elif ans1 == 1:
		print(ans2 + 1)
	else:
		print(ans2 + ans1 + ans1 * (ans1 - 1) // 2)


def pairs(leng, list1):
	count = 0
	dict1 = {}
	for i in list1:
		if i in dict1:
			dict1[i] += 1
		else:
			dict1[i] = 1
	for j in dict1:
		if dict1[j] > 1:
			x = dict1[j] - 1
			while x != 0:
				count += x
				x -= 1
	return count
n = int(input())
for i in range(n):
	leng = int(input())
	list1 = [int(a) for a in input().split()]
	print(pairs(leng, list1))


from collections import Counter as c
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	count = c(arr).values()
	ans = 0
	for j in count:
		ans += j * (j - 1) // 2
	print(ans)


from collections import Counter
for i in range(int(input())):
	l = int(input())
	s = list(map(int, input().split()))
	s = Counter(s)
	s = s.values()
	res = 0
	for val in s:
		if val > 1:
			res += val * (val - 1) // 2
	print(res)


for _ in range(int(input())):
	n = int(input())
	dic = {}
	a = list(map(int, input().split()))
	for v in a:
		if v in dic:
			dic[v] += 1
		else:
			dic[v] = 1
	good = 0
	for key in dic:
		if dic[key] > 1:
			good += dic[key] * (dic[key] - 1) // 2
	print(good)


p = int(input())
for m in range(0, p):
	k = int(input())
	n = list(map(int, input().split()[:k]))
	freq = {}
	for i in n:
		if i in freq:
			freq[i] += 1
		else:
			freq[i] = 1
	pairsum = 0
	for i in freq:
		pairsum += freq[i] * (freq[i] - 1) // 2
	print(pairsum)


for x in range(int(input())):
	n = int(input())
	a = [int(d) for d in input().split()]
	dictt = {}
	for char in a:
		if char not in dictt:
			dictt[char] = 1
		else:
			dictt[char] += 1
	final = 0
	for key in dictt:
		if dictt[key] >= 2:
			d = dictt[key]
			final += d * (d - 1) // 2
	print(final)


import math
for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	dic = {}
	for x in range(N):
		if A[x] not in dic:
			dic[A[x]] = 1
		else:
			dic[A[x]] += 1
	keys = list(dic.keys())
	freq = 0
	for z in keys:
		freq += math.comb(dic[z], 2)
	print(freq)


import pandas as pd
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	count = pd.Series(arr).value_counts()
	for j in count:
		ans = ans + j * (j - 1) // 2
	print(ans)


from collections import Counter as p
for i in range(int(input())):
	s = int(input())
	a = list(map(int, input().split()))
	b = 0
	c = p(a).values()
	for i in c:
		b += i * (i - 1) // 2
	print(b)