The Sum of Unitary Totient

Let d is the divisor of n, then d is called unitary divisor of n if the greatest common divisor of d and n/d is 1.

Let Φ^* is the unitary totient function defined as Φ^*(n)=(p₁^a₁-1)(p₂^a₂-1)...(p_r^a_r-1) for n=p₁^a₁p₂^a₂...p_r^a_r where p₁, p₂, ..., p_r are different prime numbers.

You can also find unitary totient function on this oeis page for more information.

Your task is to calculate the sum of Φ^*(1), Φ^*(2), ... Φ^*(n), which n can be up to 10⁹.

Input

There are about 200 cases. Each case is a positive integer number n in a line. (n≤ 10⁹)

Output

For each case, output the sum of Φ^*(1), Φ^*(2), ... Φ^*(n).

Sample Input

6
99
100

Sample Output

13
3475
3547