Tuấn là một học sinh rất yêu thích Tin học. Ước mơ của cậu sau 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 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\) 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 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é.

Input: Dữ liệu cho trong tệp văn bản NTCN.INP gồm một số nguyên dương \(n\ (2 ≤ n ≤ 2 \times 10)\).
Output: Kết quả ghi ra tệp văn bản NTCN.OUT 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\).

Scoring

• Có 50% số test ứng với 50% số điểm thỏa mãn: \(2 ≤ n ≤ 2000\).
• Có 40% số test ứng với 40% số điểm thỏa mãn: \(2000<n≤2×10^6\)
• Có 10% số test ứng với 10% số điểm thỏa mãn: \(2 × 10^6 <n≤2 \times 10^9\)

Example

5

4

10

4