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