Given an array A having N elements, Chef wonders how many pairs (i, j) exists such that 1 ≤ i < j ≤ N, and A_{i} \cdot A_{j} is divisible by i \cdot j. 

Can you help Chef in finding the number of such pairs?

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

- The first line of input contains a single integer T, denoting the number of test cases. The description of the T testcases follows.
- The first line of each test case contains a single integer N denoting the number of elements in A.
- The second line of each test case contains N space separated integers A_{1}, A_{2},..., A_{N}.

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

For each test case, print a single line containing one integer denoting the number of pairs that satisfies the above condition.

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

$1 ≤ T ≤ 10^{4}$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{5}$
- The sum of $N$ over all test cases does not exceed $10^{5}$

----- Sample Input 1 ------ 
3
3
1 2 3
4
2 3 5 6
5
3 9 14 6 10

----- Sample Output 1 ------ 
3
2
6

----- explanation 1 ------ 
Test Case $1$: For all possible pairs of $\{i, j\}$, $A_{i} \cdot A_{j}$ is divisible by $i \cdot j$.

Test Case $2$: The condition holds for the following two pairs of $\{i, j\}$: $\{1 , 2\}$, $\{1, 4\}$.

Difficulty: VERY_HARD
Tags: Number theory

Starter code:

Solutions:
from sys import stdin
from math import gcd
from collections import defaultdict

def make_factors(limit):
	fac = [[1] for _ in range(limit + 1)]
	for f in range(2, limit + 1):
		for mf in range(f, limit + 1, f):
			fac[mf].append(f)
	return fac
inp = stdin.readline
T = int(inp())
ans = []
factors = make_factors(100000)
for tx in range(T):
	N = int(inp())
	avail = defaultdict(dict)
	comb = 0
	for (p, a) in enumerate(map(int, inp().split()), 1):
		g = gcd(p, a)
		demand = p // g
		supplyfac = factors[a // g]
		if demand in avail:
			for f in supplyfac:
				comb += avail[demand].get(f, 0)
		for f in supplyfac:
			afac = avail[f]
			if demand in afac:
				afac[demand] += 1
			else:
				afac[demand] = 1
	ans.append(comb)
print(*ans, sep='\n')


from sys import stdin
from math import gcd
from collections import defaultdict

def make_factors(limit):
	fac = [[1] for _ in range(limit + 1)]
	for f in range(2, limit + 1):
		for mf in range(f, limit + 1, f):
			fac[mf].append(f)
	return fac
inp = stdin.readline
T = int(inp())
ans = []
factors = make_factors(100000)
avail = defaultdict(int)
for tx in range(T):
	N = int(inp())
	avail.clear()
	comb = 0
	for (p, a) in enumerate(map(int, inp().split()), 1):
		g = gcd(p, a)
		demand = p // g
		supply = a // g
		for f in factors[supply]:
			comb += avail[demand, f]
			avail[f, demand] += 1
	ans.append(comb)
print(*ans, sep='\n')


from math import *
lim = int(pow(10, 5)) + 1
factor = []
for i in range(lim):
	factor.append([1])
for i in range(2, len(factor)):
	factor[i].append(i)
	for j in range(i * 2, lim, i):
		factor[j].append(i)

def build_d(num, pos, g, d):
	num //= g
	vis = {}
	for i in range(1, int(sqrt(num)) + 1):
		if num % i == 0:
			if num // i == i:
				if i not in vis:
					vis[i] = True
					if str(i) + ' ' + str(pos // g) in d:
						d[str(i) + ' ' + str(pos // g)] += 1
					else:
						d[str(i) + ' ' + str(pos // g)] = 1
			else:
				if i not in vis:
					vis[i] = True
					if str(i) + ' ' + str(pos // g) in d:
						d[str(i) + ' ' + str(pos // g)] += 1
					else:
						d[str(i) + ' ' + str(pos // g)] = 1
				if num // i not in vis:
					vis[num // i] = True
					if str(num // i) + ' ' + str(pos // g) in d:
						d[str(num // i) + ' ' + str(pos // g)] += 1
					else:
						d[str(num // i) + ' ' + str(pos // g)] = 1
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	ans = 0
	for i in range(n):
		g = gcd(a[i], i + 1)
		for j in factor[a[i] // g]:
			tmp = str((i + 1) // g) + ' ' + str(j)
			if tmp in d:
				ans += d[tmp]
		build_d(a[i], i + 1, g, d)
	print(ans)


from os import system
from math import gcd

def IO():
	system.stdin = open('input.txt', 'r')
	system.stdout = open('output.txt', 'w')
divisor = [[1] for i in range(10 ** 5 + 3)]
for i in range(2, 10 ** 5 + 1):
	for j in range(i, 10 ** 5 + 1, i):
		divisor[j].append(i)
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	pairs = 0
	for i in range(n):
		(x, y) = (a[i], i + 1)
		z = gcd(x, y)
		x //= z
		y //= z
		for j in divisor[x]:
			if d.get(y) is not None:
				pairs += d[y].get(j, 0)
		for j in divisor[x]:
			if d.get(j) is None:
				d[j] = {}
			d[j][y] = d[j].get(y, 0) + 1
	print(pairs)


from math import gcd
divisor = [[1] for i in range(10 ** 5 + 3)]
for i in range(2, 10 ** 5 + 1):
	for j in range(i, 10 ** 5 + 1, i):
		divisor[j].append(i)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	tot = 0
	for i in range(n):
		(x, y) = (a[i], i + 1)
		z = gcd(x, y)
		x //= z
		y //= z
		for j in divisor[x]:
			if d.get(y) is not None:
				tot += d[y].get(j, 0)
		for j in divisor[x]:
			if d.get(j) is None:
				d[j] = {}
			d[j][y] = d[j].get(y, 0) + 1
	print(tot)


import sys
from math import gcd

def inp():
	return sys.stdin.readline().strip()
divisor = [[1] for i in range(10 ** 5 + 3)]
for i in range(2, 10 ** 5 + 1):
	for j in range(i, 10 ** 5 + 1, i):
		divisor[j].append(i)
t = int(inp())
while t != 0:
	n = int(inp())
	a = list(map(int, inp().split()))
	d = {}
	tot = 0
	for i in range(n):
		(x, y) = (a[i], i + 1)
		z = gcd(x, y)
		x //= z
		y //= z
		for j in divisor[x]:
			if d.get(y) is not None:
				tot += d[y].get(j, 0)
		for j in divisor[x]:
			if d.get(j) is None:
				d[j] = {}
			d[j][y] = d[j].get(y, 0) + 1
	print(tot)
	t -= 1