Phi hàm Euler

Đề bài

Đếm số lượng các số nguyên tố cùng nhau với n không vượt quá n.

Input

• Dòng duy nhất chứa số nguyên n (1 ≤ n ≤ 10^12)

Constraints

• 1 ≤ n ≤ 10^12

Output

• In ra số lượng các số nằm trong đoạn từ 1 tới n mà nguyên tố cùng nhau với n.

Sample

Input 0

36

Output 0

12

Giải thích

• Các số nguyên tố cùng nhau với 36 là: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35
• Tổng cộng có 12 số