[Bài 4 trong chuỗi bài Mỗi tuần một bài toán 2025]

Các coder có thể xem thông tin thêm tại đây: Thông tin về contest

Một số nguyên dương ~m~ được gọi là thặng dư bậc hai mod ~n~ nếu như tồn tại số nguyên ~x \in \{1,2,...,n \}~ mà ~m \equiv x^2 \pmod n~. Tiếp theo, ta chỉ quan tâm các thặng dư bậc hai ~x~ trong miền ~1,2,...,n~ mà ~\gcd(n,x)=1~, tạm gọi là thặng dư đẹp.

Ví dụ: xét mod ~9~ thì có ba thặng dư đẹp là ~1,4,7~ vì ~1 \equiv 1^2 \pmod 9, \, 4 \equiv 2^2 \pmod 9, \, 7 \equiv 4^2 \pmod 9~ và các số ~1,4,7~ đều nguyên tố cùng nhau với ~9~. Bài toán đặt ra là với số nguyên dương ~n~ cho trước, hãy đếm xem có bao nhiêu thặng dư đẹp của ~n~?

Input. Một dòng duy nhất gồm số nguyên dương ~n~ với ~1 \le n \le 10^{14}.~

Output Đáp số của bài toán.

Sample input

2016

Sample output

36