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)$.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
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)

# cook your dish here
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 :
     # print(a[i]," ",a[l])
     if psum(a[i])%psum(a[l])==0 :
      k+=1
  l+=1
 print(k)

# cook your dish here
def prime(n):
 for i in range(2,int(n/2)+1):
  if(n%i==0):
   return False;
 return True;
def psum(n):
 a=[]
 for i in range(2,n+1):
  if n%i==0:
   if prime(i):
    a.append(i)
 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 :
     # print(a[i]," ",a[l])
     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**4+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)

# cook your dish here
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()]
 #l.sort(reverse=True)
 c=0
 #  prnt(s[2])
 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:
    #print(i,j)
    c+=1 
 print(c)

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)