问题描述

给定一个正整数 n，求 1∼n 中每个数的欧拉函数之和。

输入格式

第一行一个整数 $n$。

输出格式

输出一个数字代表 1 ~ n 中所有数的欧拉函数之和。

样例

4

6

提示

样例解释

phi[1] + phi[2] + phi[3] + phi[4] = 1 + 1 + 2 + 2 = 6

数据范围

30% 的数据：$1 \le n \le 100$

50% 的数据： $1 \le n \le 1000$

100% 的数据：$1 \le n \le 10^5$