G2. Hard Formula (Hard Version)time limit per test10 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputThis 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$$$.InputThe only line contains a single integer $$$n$$$ ($$$1 \le n \le 10^{12}$$$).OutputPrint a single integer, representing $$$(\sum_{k=1}^n k\bmod\varphi(k))\bmod 2^{32}$$$.ExamplesInput5Output2
Input10000000Output2316623097
Input10000000000Output282084447