Problem Statement

$n$ dogu (clay figurines) are lined up in a row. Each dogu has a value called its "ID". Now, you want to choose 3 of the dogu and throw them away. However, the greatest common divisor of the IDs of the 3 dogu you throw away must be 1, or you will be cursed. You do not want to be cursed, so you need to choose the 3 dogu carefully. How many such ways of choosing are there?
For example, when the IDs of 3 dogu are 2,4,5 respectively, (2,5,4) and (2,4,5) are not distinguished.

Input

$n$
$a_1$
$a_2$
$.$
$.$
$.$
$a_n$

$3 \leq n \leq 100$
The ID of the $i \ (1 \leq i \leq n)$-th dogu is $a_i$. ($2 \leq a_i \leq 10^9$)
All inputs are integers.

Output

Output the number of ways to choose the dogu to throw away.
Print a newline at the end.

Sample

3
5
7
8

1

6
2
4
6
8
10
100000

0

13
810873207
437559198
824903876
399845588
927382663
413842030
854167730
733808844
798982702
1506167
352953250
191270287
464570933

225