Cho số nguyên dương $n$. 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à hai số nguyên tố cùng nhau.

Dữ liệu vào: một số nguyên dương $n$ ($2\le n\le 2\times {10}^9$)

Dữ liệu ra: một số nguyên duy nhất là số lượng các số nguyên dương $x$

Input 1

5

Output 1

4

Input 2

10

Output 2

4

Giới hạn

• Có 50% test: $2\le n\le 2000$
• Có 40% test: $2000<n<2\times {10}^6$
• Có 10% test: $2\times {10}^6<n<2\times {10}^9$