Cho số nguyên dương n. Hãy tính phi hàm Euler của n, ký hiệu là phi(n). Đây là số lượng các số nguyên dương m <= n sao cho gcd(m, n) = 1.

Dữ liệu vào: Một dòng duy nhất chứa số nguyên n.

Dữ liệu ra: Một dòng duy nhất chứa kết quả phi(n).

Ràng buộc: 1 <= n <= 10^12.

Ví dụ:

Input:

10

Output:

4

(Giải thích: Các số là 1, 3, 7, 9)