(lucky_hn.*)

Ở một vườn hoa rất đẹp của ông Nhân có \(n\) khóm hoa, khóm hoa thứ \(i\) có \(\ i\) bông hoa \((1 \leq i\ \leq n)\). Vào dịp thu hoạch, có một lái buôn muốn mua rất nhiều hoa nhưng yêu cầu ông Nhân phải chọn ra những khóm hoa may mắn. Khóm hoa may mắn là khóm hoa có số lượng bông hoa không có ước chung khác 1 với \(n\). Ông Nhân muốn đếm số lượng khóm hoa may mắn để bán cho lái buôn nhưng số lượng khóm hoa rất lớn nên ông Nhân muốn nhờ bạn tính giúp.

Yêu cầu: Bạn hãy lập trình giúp ông Nhân đếm số lượng khóm hoa may mắn.

Dữ liệu vào:

+ Một dòng duy nhất chứa số nguyên dương \(n\ \left( 2 \leq n \leq 10^{10} \right)\ \)

Kết quả: Ghi một số nguyên dương là số lượng khóm hoa thỏa mãn.

Ví dụ:

Giải thích:

- Ở test 1: Trong 13 khóm hoa có 12 khóm có số bông hoa không có ước chung khác 1 với 13 là: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.

- Ở test 2: Trong 16 khóm hoa có 8 khóm có số bông hoa không có ước chung khác 1 với 16 là: 1, 3, 5, 7, 9, 11, 13, 15.

Ràng buộc:

+ 70% số test đầu tiên có \(n \leq 10^{6}.\)

+ 30% số test tiếp theo có \(n \leq 10^{10}.\)