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 * 10^9)~,

Output

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

Scoring

• Subtask ~1~ (~50\%~ số điểm): ~2 \le N\le 20000~.
• Subtask ~2~ (~40\%~ số điểm): ~20000 \le N\le 2 * 10^6~.
• Subtask ~3~ (~10\%~ số điểm): ~2 * 10^6 \le N \le 2 * 10^9~

Ví dụ

Input

5

Output

4