G2. 困难公式（困难版本）
每个测试点的时间限制：10 秒
每个测试点的内存限制：1024 MB

这是该问题的困难版本。两个版本的区别在于，此版本中 $n$ 的范围限制更大，且时间限制也更高。只有解决了该问题的所有版本，你才能进行 Hack。

---

题目描述

给定一个整数 $n$，你需要计算

$$\left( \sum_{k=1}^{n} k \bmod \varphi(k) \right) \bmod 2^{32} $$

其中 $\varphi(k)$ 表示不超过 $k$ 且与 $k$ 互质的正整数的个数。

---

输入格式

输入只有一行，包含一个整数 $n$（$1 \le n \le 10^{12}$）。

---

输出格式

输出一个整数，表示

$$\left( \sum_{k=1}^{n} k \bmod \varphi(k) \right) \bmod 2^{32} $$

---

样例

样例输入 1

5

样例输出 1

2

样例输入 2

10000000

样例输出 2

2316623097

样例输入 3

10000000000

样例输出 3

282084447