CF2081G2 Hard Formula (Hard Version)

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 $ .

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

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