Time Limit: 1s → 0.5s

Longge 的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数 $N$，你需要求出 $\sum_{i=1}^N \gcd(i, N)$。

输入格式

一个整数，为 $N$。

输出格式

一个整数，为所求的答案。

样例数据

样例输入

6

样例输出

15

子任务

对于 $60\%$ 的数据，$0 < N \leq 2^{16}$。

对于 $100\%$ 的数据，$0 < N \leq 2^{32}$。