Link my group on LQDOJ

Nguồn: Apex Cup 2026 in ledinhbaonam group(here: ledinhbaonam group)

Nam là một học sinh yếu, môn nào cũng tạch. Một hôm, giáo viên thấy bạn ấy khá tội (lỗi) khi được con số 0 tròn trĩnh trong bài kiểm tra, nên cô đã cho bạn 1 bài khá dễ, nếu làm được thì cô sẽ cho bạn 1 điểm, còn ko làm đc thì vẫn giữ nguyên con số 0 đấy. Bài toán như sau:

Đếm trong 1 đoạn \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) có bao nhiêu cặp số nguyên tố cùng nhau.

Biết rằng, \(a\) và \(b\) là 1 cặp số nguyên tố cùng nhau khi \(gcd(a, b) = 1\)

Nhưng vì bản chất Nam không thể giải nó, nên Nam đã lén đăng bài lên mạng nhờ các bạn coders giải giúp, các bạn hãy giúp Nam nhé!

Input

• Dòng thứ nhất ghi ra 1 số nguyên dương \(N\) (\(1 \le N \le 10^5\))
• Dòng thứ hai ghi ra \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\))

Output

• Đếm số cặp số nguyên tố cùng nhau trong đoạn.

Example

3
2 7 8

2