背景

$\color{black}{\text{W}}\color{red}{\text{iš'adel}}$ 有 $n$ 个祖宗，第 $k$ 个祖宗的攻击力为 $k\bmod\varphi(k)$，其中 $\varphi(n)$ 为 $[1,n]$ 中与 $n$ 互质的非零自然数个数。

由于 $\color{black}{\text{D}}\color{red}{\text{octor}}$ 是 $\text{DPS Lover}$，他想计算 $\color{black}{\text{W}}\color{red}{\text{iš'adel}}$ 的 $\text{DPS}$ 就得先计算她所有祖宗的攻击力之和。但是 $\color{black}{\text{D}}\color{red}{\text{octor}}$ 最近沉迷游玩萨卡兹的无终奇语无法自拔，于是他请你来帮他计算 $\color{black}{\text{W}}\color{red}{\text{iš'adel}}$ 所有祖宗的攻击力之和。

因为 $\color{black}{\text{D}}\color{red}{\text{octor}}$ 是前文明最后的人类，实力非凡，所以你只需要输出答案对 $2^{32}$ 取模的结果他就可以计算出 $\color{black}{\text{W}}\color{red}{\text{iš'adel}}$ 的 $\text{DPS}$。

题目描述

请计算：

输入格式

一个整数表示 $N$。

输出格式

一个数字表示结果。

10

8

10000000000

282084447

1000000000000

3875137357

10000000000000

158839419

提示

• Subtask1（10pts）$N\leq 10^{8}$，时间限制 $2s$。
• Subtask2（10pts）$N\leq 10^{10}$，时间限制 $2s$。
• Subtask3（20pts）$N\leq 10^{11}$，时间限制 $2s$。
• Subtask4（20pts）$N\leq 10^{12}$，时间限制 $3s$。
• Subtack5（40pts）$N\leq 10^{13}$，时间限制 $5s$。

$\text{PRTS}$ 认为，整形除法的常数远大于浮点除法，因此在大量需要整形除法的场景中请尽可能地使用浮点除法。