Mandarin chinese
, Russian and Vietnamese as well.
Let's denote $S(x)$ by the sum of prime numbers that divides $x$.
You are given an array $a_1, a_2, \ldots, a_n$ of $n$ numbers, find the number of pairs $i, j$ such that $i \neq j$, $a_i$ divides $a_j$ and $S(a_i)$ divides $S(a_j)$.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- First line of each testcase contains one integer $n$ — number of elements of the array.
- Second line of each testcase contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$.

-----Output:-----
For each testcase, output in a single line number of pairs that each of it satisfies given conditions.

-----Constraints-----
- $1 \leq T \leq 100$
- $2 \leq n, a_i \leq 10^6$
- the sum of $n$ for all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #2 (20 points): $2 \leq n \leq 100$, $2 \leq a_i \leq 10^4$
Subtask #2 (80 points): original contsraints

-----Sample Input:-----
1
5
2 30 2 4 3

-----Sample Output:-----
6

-----EXPLANATION:-----
$S(2) = 2, S(30) = 2 + 3 + 5 = 10, S(4) = 2, S(3) = 3$. So using this information, the pairs of indicies are $(1,2)$, $(1, 3)$, $(1, 4)$, $(3, 1)$, $(3, 2)$, $(3, 4)$.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def prime_factors(n):
	i = 2
	factors = set()
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.add(i)
	if n > 1:
		factors.add(n)
	return factors
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	s = []
	for i in range(n):
		s.append(sum(prime_factors(a[i])))
	for i in range(n):
		for j in range(n):
			if i != j and a[j] % a[i] == 0 and (s[j] % s[i] == 0):
				ans = ans + 1
	print(ans)


from math import sqrt

def prime(n):
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

def psum(n):
	a = []
	for i in range(2, int(n / 2) + 1):
		if n % i == 0:
			if prime(i):
				a.append(i)
	if prime(n):
		a.append(n)
	return sum(a)
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = 0
	k = 0
	while l < len(a):
		for i in range(len(a)):
			if i != l:
				if a[i] % a[l] == 0:
					if psum(a[i]) % psum(a[l]) == 0:
						k += 1
		l += 1
	print(k)


import bisect
import sys
import math
t = int(input())
M = 2000001
s = [0 for x in range(M)]
for i in range(2, M):
	if s[i] == 0:
		s[i] = i
		for j in range(i * 2, M, i):
			s[j] += i
while t:
	n = int(input())
	a = [int(x) for x in input().split()]
	dict = {}
	m = 0
	for x in a:
		m = max(x, m)
		if x in dict:
			dict[x] += 1
		else:
			dict[x] = 1
	count = 0
	for k in dict.keys():
		d = dict[k] * (dict[k] - 1)
		count += d
		for i in range(2, math.ceil(m / k) + 1):
			if i * k in dict and s[i * k] % s[k] == 0:
				d = dict[k] * dict[i * k]
				count += d
	sys.stdout.write(str(count) + '\n')
	t -= 1


p = 10 ** 6 + 5

def Sieve():
	l = [True] * p
	s = [0] * p
	for i in range(2, p):
		if l[i]:
			for j in range(i, p, i):
				s[j] += i
				l[j] = False
		i += 1
	l[0] = l[1] = False
	return (l, s)
(isprime, s) = Sieve()
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	c = Counter(l)
	ans = 0
	maxi = max(l)
	for i in range(2, maxi + 1):
		if c[i] > 0:
			for j in range(i, maxi + 1, i):
				if s[j] % s[i] == 0:
					ans += c[i] * c[j]
	ans -= n
	print(ans)


p = 10 ** 5 + 5

def Sieve():
	l = [True] * p
	s = [0] * p
	for i in range(2, p):
		if l[i]:
			for j in range(i, p, i):
				s[j] += i
				l[j] = False
		i += 1
	l[0] = l[1] = False
	return (l, s)
(isprime, s) = Sieve()
from collections import defaultdict
good = defaultdict(list)
for i in range(2, p):
	for j in range(i, p, i):
		if s[j] % s[i] == 0:
			good[i].append(j)
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	c = Counter(l)
	ans = 0
	for i in range(2, p):
		if c[i]:
			for j in good[i]:
				ans += c[i] * c[j]
	ans -= n
	print(ans)


p = 10 ** 6 + 5

def Sieve():
	l = [True] * p
	s = [0] * p
	for i in range(2, p):
		if l[i]:
			for j in range(i, p, i):
				s[j] += i
				l[j] = False
		i += 1
	l[0] = l[1] = False
	return (l, s)
(isprime, s) = Sieve()
for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	c = 0
	for i in range(n):
		for j in range(n):
			if s[l[j]] % s[l[i]] == 0 and l[j] % l[i] == 0 and (i != j):
				c += 1
	print(c)