Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
135 - ZOJ Monthly, August 2014 - K
The Sum of Unitary Totient

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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)=(p1a1-1)(p2a2-1)...(prar-1) for n=p1a1p2a2...prar where p1, p2, ..., pr 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 109.

Input

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

Output

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

Sample Input

6
99
100

Sample Output

13
3475
3547

Author: ZHOU, Yuchen
Submit    Status