Tuấn là một học sinh yêu thích Tin học. Gần đây, Tuấn nghe nói về sức mạnh của robot thông minh ChatGPT nên đã đố ChatGPT một bài toán 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 thỏa 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 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.

Yêu cầu: 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 với các số n lớn hơn nhé!

Dữ liệu vào (Input): Nhập từ bàn phím một số nguyên dương n ~(2 \le n \le 2 \times 10^9)~.

Kết quả ra (Output): In ra màn hình 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.

Giới hạn:

• Có 50% số điểm: ~2 \le n \le 2000~
• Có 40% số điểm: ~2000 < n \le 2 \times 10^6~
• Có 10% số điểm: ~2 \times 10^6 < n \le 2 \times 10^9~

Ví dụ: