Geometric Mean

Alice found $N$ cards. There is a number written on each card. While she was waiting for her friends to play some game, she decided to count the number of ways she can choose $4$ cards, such that the geometric $mean^1$ of the numbers on the selected cards is an integer.
Can you help her to count the number of quadruples when the geometric mean is integer?

Formally, given an array $V$ of length $N$, we want to count the quadruples $0 \leq i < j < k < l \leq N−1$ such that $\sqrt[4]{ V [i] \cdot V [j] \cdot V [k] \cdot V [l]}$ is an integer.

Input data

The input file consists of:

• a line containing integer $N$: the number of the cards.
• a line containing the $N$ integers $V_0, . . . , V_{N−1}$: the numbers written on the cards.

Output data

The output file must contain a single line consisting of a $64$-bit integer: the number of quadruples of cards with integer geometric mean.

Constraints and clarifications

• $1 \leq N \leq 1 \ 000$.
• $1 \leq V_i \leq 1 \ 000 \ 000$ for each $i = 0 . . . N−1$.
  Your program will be tested against several test cases grouped in subtasks. In order to obtain the score of a subtask, your program needs to correctly solve all of its test cases.

$^1$ The geometric mean of $a, b, c, d$ is $\sqrt[4]{abcd}$ .

Example 1

stdin

8
1 6 4 5 7 10 15 14

stdout

0

Explanation

In the first sample case we can not choose $4$ numbers, such that their geometric mean is integer.

Example 2

stdin

7
2024 2024 2024 2024 2024 2024 2024

stdout

35

Explanation

In the second sample case any four-tuple is good, so the answer is $\binom{7}{4} = 35$

Example 3

stdin

8
1 2 4 8 16 32 64 128

stdout

18

Explanation

In the third sample case we have $18$ good quadruples: $(1, 2, 8, 16)$, $(1, 2, 16, 128)$, $(1, 2, 32, 64)$, $(1, 4, 8, 128)$, $(1, 4, 16, 64)$, $(1, 8, 16, 32)$, $(1, 8, 64, 128)$, $(1, 16, 32, 128)$, $(2, 4, 8, 64)$, $(2, 4, 16, 32)$, $(2, 4, 64, 128)$, $(2, 8, 32, 128)$, $(2, 16, 32, 64)$, $(4, 8, 16, 128)$, $(4, 8, 32, 64)$, $(4, 32, 64, 128)$, $(8, 16, 64, 128)$.
For example, $(1, 2, 4, 32)$ is good, because $\sqrt[4]{ 1 \cdot 2 \cdot 4 \cdot 32}= 4$.