G2. Hard Formula (Hard Version)
time limit per test
10 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The difference between the versions is that in this version, the limit on $$$n$$$ and the time limit are higher. 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^{12}$$$).

Output

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

Examples
Input
5
Output
2
Input
10000000
Output
2316623097
Input
10000000000
Output
282084447