Kết bạn

Tại vùng đất công nghệ nơi CLB CHTcoder đặt trụ sở, cư dân sống rất chan hòa và tích cực.
Vùng đất này có \(n\) người dân, mỗi người đều sở hữu một chỉ số đại diện cho bản thân gọi là Social Credit.
Điểm Social Credit của các cư dân là các số nguyên dương phân biệt từ \(1\) đến \(n\), trong đó người đứng đầu bảng xếp hạng có điểm bằng đúng \(n\).

Quy tắc giao tiếp: Người đứng đầu chỉ có thể kết bạn với một cư dân khác nếu điểm Social Credit của hai người là hai số nguyên tố cùng nhau (nghĩa là \(\gcd(n, x) = 1\)).

Bạn hãy giúp người đứng đầu CLB tính xem có bao nhiêu cư dân trong vùng đất có thể trở thành bạn của anh ấy.

Input

Đọc từ file văn bản KETBAN.INP:

• Một số nguyên dương duy nhất \(n\) (\(1 < n \le 10^{12}\)).

Output

Ghi ra file văn bản KETBAN.OUT:

• Một số nguyên dương duy nhất là số lượng bạn bè mà người đứng đầu có thể kết thân.

Example

4

2

Scoring

• \(60\%\) số test đầu tiên của bài toán ứng với \(60\%\) số điểm có: \(n \le 10^5\).
• \(40\%\) số test còn lại của bài toán ứng với \(40\%\) số điểm có: \(n \le 10^{12}\).