Hai số nguyên tố cùng nhau là hai số có ước chung lớn nhất bằng 1.

Yêu cầu: Cho số nguyên dương n. Tìm số lượng các số nguyên dương x nhỏ hơn n thoả măn: x và n là hai số nguyên tố cùng nhau.

Dữ liệu: Đọc từ thiết bị chuẩn (bàn phím) số nguyên dương n (2 ≤ n ≤ 2 x 10^6)

Kết quả: Một số nguyên duy nhất là số lượng các số nguyên dương x, nhỏ hơn n và nguyên tổ cùng nhau với n.

Ví dụ:

Input 01:

4

Output 01:

2

Giải thích: n = 4, trong 3 số 1, 2, 3 nhỏ hơn n, có 2 số thoa mãn: x = 1, 3 là các số nguyên tố cùng nhau với n.

Input 02:

15

Output 02:

8

Giải thích: n = 15, trong 14 số 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 nhỏ hơn n, có 8 số thoa mãn: x = 1, 2, 4, 7, 8, 11, 13, 14 là các số nguyên tố cùng nhau với n.

Giới hạn:

• Có 70% số điểm thoả mãn: 2 ≤ n ≤ 2 x 10^3.

• Có 30% số điểm thoả mãn: 2 x 10^3 < n ≤ 2 x 10^6.