Mô tả và yêu cầu

Tuấn là một học sinh giỏi rất yêu thích Tin học. Ước mơ của cậu này là trở
thành một lập trình viên tài năng. Tuấn thường xuyên tìm hiểu các thông tin, sự kiện
liên quan đến Công nghệ. Một sự kiện công nghệ nổi tiếng trên toàn thế giới trong
thời gian gần đây là sự ra mắt robot thông minh ChatGPT của công ty công nghệ
OpenAI. Tuấn cũng rất tò mò về ChatGPT nên đã sử dụng để giải bài toán. Bài toán
mà Tuấn đưa ra cho ChatGPT như sau:
Cho số nguyên dương n. Tìm số lượng các số nguyên dương x nhỏ hơn n thoả
mãn: x và n là hai số nguyên tố cùng nhau (tức là ước chung lớn nhất của x và n
bằng 1).
Thật là thú vị, khi Tuấn nhập n = 5. ChatGPT đưa ra kết quả là : Có 4 số, cụ thể
là các số: 1, 2, 3, 4.
Tuấn muốn các bạn lập trình giải bài toán này để cùng kiểm tra kết quả của
ChatGPT nhé.
Dữ liệu: Vào từ thiết bị nhập chuẩn chứa một số nguyên dương n (2 ≤ n ≤ 109).

Kết quả: Ghi ra thiết bị xuất chuẩn gồm một số nguyên duy nhất là số lượng
các số nguyên dương x, nhỏ hơn n và nguyên tố cùng nhau với n.
Ví dụ 1:
INPUT OUTOUT Giải thích
5 4 n = 5, trong 4 số 1, 2, 3,
4 nhỏ hơn n. Có 4 số
thoả mãn x = 1, 2, 3, 4
là các số nguyên tố cùng
nhau với n.
Ví dụ 2:
INPUT OUTOUT Giải thích
10 4 n = 10, trong 9 số 1, 2,
3, 4, 5, 6, 7, 8, 9 nhỏ
hơn n. Có 4 số thoả mãn
x = 1, 3, 7, 9 là các số
nguyên tố cùng nhau
với n.

Giới hạn và chấm điểm

Có 50% số test ứng với 50% số điểm thoả mãn : 2 ≤ n ≤ 2000.
Có 40% số test ứng với 40% số điểm thoả mãn : 2000 < n ≤ 2 . 106.
Có 10% số test ứng với 10% số điểm thoả mãn : 2.106 < n ≤ 2.109.