Cho dãy \(a_1, a_2, \dots, a_N\). Đếm số cặp \((i, j)\) với \(1 \le i < j \le N\) sao cho \(\gcd(a_i, a_j) = 1\).

Định dạng đầu vào

• Dòng đầu: số nguyên \(N\) (\(1 \le N \le 10^5\)).
• Dòng hai: \(N\) số nguyên \(a_i\) (\(1 \le a_i \le 10^5\)).

Định dạng đầu ra

• Một số nguyên là số cặp thỏa mãn.

Ví dụ

Input:

5
2 3 4 5 6

Output:

5

Giải thích: Các cặp: (2,3), (2,5), (3,4), (3,5), (4,5) - tổng cộng 5 cặp.

Ràng buộc

• 100% số điểm: \(N \le 10^5, a_i \le 10^5\).
• 60% số điểm: \(N \le 2000\).