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

Input Format

Số nguyên duy nhất n.(1≤n≤10^12)

Constraints

.

Output Format

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.

Ví dụ:

Dữ liệu vào

36

Dữ liệu ra

12