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 \lt n \lt 2 \times 10^6\)
• Có 10% test: \(2 \times 10^6 \lt n \lt 2 \times 10^9\)