G2. Сложная формула (Сложная версия)
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии ограничение на $$$n$$$ и ограничение по времени выше. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Более формально, вам дано целое число $$$n$$$, и вам нужно вычислить $$$(\sum_{k=1}^n k\bmod\varphi(k))\bmod 2^{32}$$$, где $$$\varphi(k)$$$ равняется количеству положительных целых чисел, не превышающих $$$k$$$, которые взаимно просты с $$$k$$$.

Входные данные

Единственная строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^{12}$$$).

Выходные данные

Выведите одно целое число, представляющее $$$(\sum_{k=1}^n k\bmod\varphi(k))\bmod 2^{32}$$$.

Примеры
Входные данные
5
Выходные данные
2
Входные данные
10000000
Выходные данные
2316623097
Входные данные
10000000000
Выходные данные
282084447