Cho số nguyên dương \(N\). Tính tổng: \(S = \sum_{i=1}^{N} \gcd(i, N)\).

Định dạng đầu vào

• Một dòng chứa số nguyên \(N\) (\(1 \le N \le 10^{12}\)).

Định dạng đầu ra

• Một số nguyên duy nhất là \(S\).

Ví dụ

Input:

6

Output:

15

Giải thích: \(\gcd(1,6)+\gcd(2,6)+\gcd(3,6)+\gcd(4,6)+\gcd(5,6)+\gcd(6,6) = 1+2+3+2+1+6 = 15\).

Ràng buộc

• 100% số điểm: \(N \le 10^{12}\).
• 50% số điểm: \(N \le 10^6\).