Read problems statements in Mandarin Chinese and Russian.

You are given a sequence a_{1}, a_{2}, ..., a_{N}. Count the number of triples (i, j, k) such that 1 ≤ i < j < k ≤ N and GCD(a_{i}, a_{j}, a_{k}) = 1. Here GCD stands for the Greatest Common Divisor.

------ Input ------

The first line of input contains a single integer N - the length of the sequence.

The second line contains N space-separated integers - a_{1}, a_{2}, ..., a_{N} respectively.

------ Output ------

Output the required number of triples on the first line of the output.

------ Constraints ------

$1 ≤ N ≤ 100 : 22 points.$
$1 ≤ N ≤ 1000 : 23 points.$
$1 ≤ N ≤ 10^{5} : 55 points.$
$1 ≤ a_{i} ≤ 10^{6}$

------ Example ------

Input:
4
1 2 3 4

Output:
4

------ Explanation ------

Any triple will be a coprime one.

见题面

见题面