UVa 10820

Summary

Given a number ${\displaystyle N}$, find the cumulative sum of the number of numbers relatively prime to ${\displaystyle \leq N}$.

Explanation

Use Euler's Phi function, and cache the answers.

${\displaystyle f(n)=f(n-1)+2\phi (n)}$

Input

100
1
2
3
4
5
10
20
30
200
300
1000
2000
3000
50000
0


Output

6087
1
3
7
11
19
63
255
555
24463
54795
608383
2433175
5472375
1519848527