Zincate là một học sinh trung học có niềm đam mê với tin học. Zincate thường tự học các ngôn ngữ lập trình và thử nghiệm các dự án nhỏ trên máy tính của Zincate. Một ngày, Zincate nhận được một Zincate từ một hacker nổi tiếng có tên là Brxdie. Hacker này nói rằng anh ta đã phát hiện ra một lỗ hổng trong hệ thống bảo mật của một công ty lớn, và muốn Zincate giúp anh ta tấn công vào đó. Anh ta nói rằng nếu Zincate làm được, anh ta sẽ chia sẻ cho Zincate một phần của số tiền mà anh ta đánh cắp được. Tuy nhiên, để chứng minh khả năng của Zincate, anh ta yêu cầu Zincate phải giải được một bài toán tin học do anh ta đưa ra:
Cho số nguyên dương . Hãy tìm số lượng số thoả mãn và là hai số nguyên tố cùng nhau. Biết hai số nguyên tố cùng nhau là hai số có ước chung lớn nhất bằng .
Các bạn hãy giúp Zincate trả lời câu hỏi trên nhé!
Dữ liệu vào
Một dòng duy nhất chứa số nguyên dương
Dữ liệu ra
Một dòng duy nhất chứa số lượng số nguyên dương thoả mãn.
Ví dụ
Dữ liệu vào
6
Dữ liệu ra
2
Giới hạn
số test tương ứng số điểm có ;
số test khác tương ứng số điểm không có ràng buộc gì thêm
