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\).