Background

Longge excels at mathematics, and he enjoys tackling challenging math problems.

Problem Description

Here is the problem: Given an integer $n$, you need to compute $\sum\limits_{i=1}^n \gcd(i, n)$, where $\gcd(i, n)$ denotes the greatest common divisor of $i$ and $n$.

Input Format

The input consists of a single line containing the integer $n$.

Output Format

Output a single integer on one line representing the answer.

6

15

Hint

Constraints

• For $60\%$ of the testdata, it is guaranteed that $n \leq 2^{16}$.
• For $100\%$ of the testdata, it is guaranteed that $1 \leq n < 2^{32}$.

Translated by ChatGPT 5