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 kà ước chung lớn nhất của \(x\) và \(n\) bằng 1)

Dữ liệu vào:

+ Ghi số nguyên dương \(n\ (n \leq 10^{9})\)

Kết quả:

+ Ghi một số nguyên duy nhất cho biết kết quả bài toán

Ví dụ:

Ràng buộc:

+ Có 50% số test tương ứng 50% số điểm có \(2 \leq n \leq 2000\);

+ Có 40% số test khác ứng với 40% số điểm có \(2 \leq n \leq 2 \times 10^{6}\);

+ Có 10% số test còn lại tương ứng 10% số điểm có \(2 \leq 2 \times 10^{9}\).