Longge is excellent at mathematics and enjoys challenging himself with difficult math problems. Now, here is the problem: given an integer $N$, you need to calculate $\sum_{i=1}^N \gcd(i, N)$.
Input
A single integer $N$.
Output
A single integer representing the result.
Examples
Input 1
6Output 1
15Subtasks
For $60\%$ of the data, $0 < N \leq 2^{16}$.
For $100\%$ of the data, $0 < N \leq 2^{32}$.