Một phân số được gọi là phân số tối giản nếu ước chung lớn nhất của tử số và mẫu số bằng 1.

Yêu cầu: Cho trước một số nguyên dương N. Hãy đếm xem có bao nhiêu phân số dương bé hơn 1, có mẫu là N và là phân số tối giản.

Dữ liệu vào: Đọc từ file văn bản PSTG.INP một số nguyên dương N                  (N ≤ 10¹⁶).

Dữ liệu ra: Ghi ra file văn bản PSTG.OUT số nguyên M là số lượng phân số theo yêu cầu trên.

Ví dụ:

Giải thích: Có 6 phân số dương bé hơn 1 có mẫu bằng 9 và là phân số tối giản là 1/9;2/9;4/9;5/9;7/9;8/9