Prime divisors

All submissions for this problem are available.
Read problems statements in Hindi, 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$ spaceseparated 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)$.Author:  fekete 
Editorial  https://discuss.codechef.com/problems/PRMDIV 
Tags  easy, fekete, fekete, likecs, ltime62, sieve 
Date Added:  28072018 
Time Limit:  1.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 