Cho số nguyên $N$, hãy tìm số lượng các số nguyên dương $X$ nhỏ hơn $N$ thỏa mãn: $X$ và $N$ là $2$ số nguyên tố cùng nhau. (Tức là UCLN của $X$ và $N$ bằng $1$)

Input

• Một dòng duy nhất là số nguyên $N(N\le 2\ast {10}^9)$,

Output

• Số lượng các số nguyên dương $X$

Scoring

• Subtask $1$ ($50\mathrm{\%}$ số điểm): $2\le N\le 20000$.
• Subtask $2$ ($40\mathrm{\%}$ số điểm): $20000\le N\le 2\ast {10}^6$.
• Subtask $3$ ($10\mathrm{\%}$ số điểm): $2\ast {10}^6\le N\le 2\ast {10}^9$

Ví dụ

Input

5

Output

4