[SDOI2012]Longge的问题

题目描述

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

输入输出格式

输入格式


一行一个整数,为 $N$。

输出格式


一行一个整数,为所求的答案。

输入输出样例

输入样例 #1

6

输出样例 #1

15

说明

对于 $60\% $ 的数据,$1\leq N\leq 2^{16}$。 对于 $100\% $ 的数据,$1\leq N\leq 2^{32}$。