Cặp số nguyên tố cùng nhau

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\) (\(2 \leq n \leq 2 \times 10^9\)). Đếm số lượng số nguyên dương \(x\) nhỏ hơn \(n\) mà nguyên tố cùng nhau với \(n\) (tức là \(UCLN(x,n)=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

Vào từ file NTCN.INP gồm một số nguyên dương \(n\) \((2 \leq n \leq 2 \times 10^9)\).

Output

Ghi ra file 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\).

Example

5

4

10

4

Scoring

• Có \(50\%\) số test tương ứng với \(50\%\) số điểm có \(n \leq 2000\).
• Có \(40\%\) số test tương ứng với \(40\%\) số điểm có \(2000 < n \leq 2 \times 10^6\).
• Có \(10\%\) số test tương ứng với \(10\%\) số điểm có \(2 \times 10^6 < n \leq 2 \times 10^9\).