GCD SUM

题目描述

求 $$\sum_{i=1}^n \sum_{j=1}^n \gcd(i, j)$$

输入输出格式

输入格式


第一行一个整数 $n$。

输出格式


第一行一个整数表示答案。

输入输出样例

输入样例 #1

2

输出样例 #1

5

说明

对于 $30\%$ 的数据，$n\leq 3000$。 对于 $60\%$ 的数据，$7000\leq n\leq 7100$。 对于 $100\%$ 的数据，$n\leq 10^5$。