Hàm phi Euler \(\varphi(N)\) là một hàm số học quan trọng trong mật mã học (đặc biệt là thuật toán RSA), định nghĩa là số lượng số nguyên dương nhỏ hơn hoặc bằng \(N\) và nguyên tố cùng nhau với \(N\). Hãy viết chương trình tính giá trị \(\varphi(N)\) với \(N\) có thể cực kỳ lớn.

Định dạng đầu vào

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

Định dạng đầu ra

• Một số nguyên duy nhất là kết quả của hàm \(\varphi(N)\).

Ví dụ

Input:

12

Output:

4

Giải thích

Các số nguyên tố cùng nhau với 12 và không vượt quá 12 là: \(\{1, 5, 7, 11\}\), tổng cộng có 4 số.

Ràng buộc

• 40% số điểm ứng với \(N \le 10^6\).
• 60% số điểm còn lại không có ràng buộc gì thêm.