ID: 2815

Type: Default

1000ms

256MiB

Difficulty: (None)

Uploaded By:

Background

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

Input

共一行，包含一个整数 $n$ 。

Output

共一行，包含一个整数，表示 $1\sim n$ 中每个数的欧拉函数之和。

Samples

Limitation

$1≤n≤10^6$