Jhakaas, recently being fascinated by prime numbers came up with a problem and asked Apptica to solve it. Apptica is working on Machine Learning Project and passed it to Altaireon to solve.

He is given an array A of N integers and the definition of two functions g and f as follows:

$g(i, j) = \text{Number of unique common prime factors between } A_i \text{ and } A_j$
$f(i, j) = 1 \text{ if } g(i, j) \leq 1 \text{ otherwise } 0$

You are Altaireon, and now you have to calculate

$\sum f(i, j) \text{ such that } 1 \leq i \lt j \leq N$

Input:
First line contains N, size of the array A. Next line contains N space separated positive integers, denoting elements of A.

Output:
Print a single integer, denoting the required answer.

Constraints:
$2 \leq N \leq 3 \cdot 10^5$
$1 \leq A_i \leq 3 \cdot 10^4$