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