This is the easy version of the problem. The difference between the versions is that in this version, the limits on $n$ and the time limit are smaller. You can hack only if you solved all versions of this problem.

You are given an integer $n$, and you need to compute $(\sum_{k=1}^n k\bmod\varphi(k))\bmod 2^{32}$, where $\varphi(k)$ equals the number of positive integers no greater than $k$ that are coprime with $k$.

Input

The only line contains a single integer $n$ ($1 \le n \le 10^{10})$.

Output

Print a single integer, representing $(\sum_{k=1}^n k\bmod\varphi(k))\bmod 2^{32}$.