Hai số nguyên dương được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng ~1~.

Yêu cầu

Cho số nguyên dương ~n~. Hãy đếm số lượng số nguyên dương ~x<n~ sao cho ~x~ và ~n~ nguyên tố cùng nhau.</p>

Input

Một dòng duy nhất chứa số nguyên dương ~n~ ~(2 \le n \le 2\times 10^6)~.

Output

In ra số lượng số nguyên dương nhỏ hơn ~n~ và nguyên tố cùng nhau với ~n~.

Subtask

• Subtask ~1~ có ~70\%~ số điểm: ~2 \le n \le 2\times 10^3~.
• Subtask ~2~ có ~30\%~ số điểm: ~2\times 10^3 < n \le 2\times 10^6~.

Ví dụ 1

4

2

Ví dụ 2

15

8