Những Cặp Không Chung Ước · canuc80k7000

Cho một dãy số nguyên dương, đếm số cặp chỉ số khác nhau không xét thứ tự mà hai giá trị tương ứng nguyên tố cùng nhau.

Hai giá trị được gọi là nguyên tố cùng nhau khi ước chung lớn nhất của chúng bằng $1$ . Mỗi cặp chỉ số chỉ được tính một lần.

Input

Dòng đầu chứa số phần tử $n$ .
Dòng tiếp theo chứa $n$ số nguyên dương $a_{i}$ .

Output

In một số nguyên là số cặp chỉ số $i < j$ thỏa $g cd (a_{i}, a_{j}) = 1$ .

Constraints

$1 \leq n \leq 1 0^{5} .$
$1 \leq a_{i} \leq 1 0^{6} .$

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 2000$ và $a_{i} \leq 5000$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

6
2 3 4 9 10 25

Output

Giải thích: Trong $15$ cặp chỉ số, có $10$ cặp có ước chung lớn nhất bằng $1$ ; năm cặp còn lại cùng chia hết cho $2, 3$ hoặc $5$ . Vì vậy kết quả cần in là $10$ .