Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 3808
The Sum of Unitary Totient

Time Limit: 5 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
Source: ZOJ Monthly, August 2014
Submit    Status