Migrated from Lutece 1564 GC?(X,Y)

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

One positive integer can be represented by the product of some prime numbers.

Sort the prime numbers, such like $60=2\times 2\times 3\times 5$, $180=2\times 2\times 3\times 3\times 5$.

The $GCP$(Greatest Common Prefix) of two positive integers is defined as the longest prefix of the multiplication of sorted prime numbers.

For example, $GCP(60,180)=Longest\_Prefix(2\times 2\times 3\times 5,2\times 2\times 3\times 3\times 5)=2\times 2\times 3=12$.

Now, for a given array $A_i$, calculate $\sum_{1\leq i<j\leq N}{GCP(A_i,A_j)}$.

Input

The first line contains a number $N$.

The second line contains $N$ integers $A_i$.

$1\leq N\leq 10^5, 1\leq A_i\leq 10^7$

Output

Output the sum described above.

Samples

5
1 2 8 5 10

13

Note

In the sample,

$GCP(1,2)=GCP(1,8)=GCP(1,5)=GCP(1,10)=GCP(2,5)=GCP(8,5)=GCP(5,10)=1$,

$GCP(2,8)=GCP(2,10)=GCP(8,10)=2$.

Resources

The 15th UESTC Programming Contest Preliminary