Problem L

Irreducible Basic Fractions

Input: standard input

Output: standard output

Time Limit: 4 seconds

A fraction m / n is basic if 0 <= m < n and it is irreducible if gcd(m, n) = 1. Given a positive integer n, in this problem you are required to find out the number of irreducible basic fractions with denominator n .

For example, the set of all basic fractions with denominator 12, before reduction to lowest terms, is

Reduction yields

Hence there are only the following 4 irreducible basic fractions with denominator 12

Input

Each line of the input contains a positive integer n (< 1000000000) and the input terminates with a value 0 for n (do not process this terminating value).

Output

For each n in the input print a line containing the number of irreducible basic fractions with denominator n

Sample Input

12
123456
7654321
0

Sample Output

4
41088
7251444

---

Rezaul Alam Chowdhury
 
“I shot an arrow into the air,
It fell to earth, I knew not where;
For, so swiftly it flew, the sight
Could not follow it in its flight.
 
   I breathed a song into the air,     
It fell to earth, I knew not where;
For who has sight so keen and strong,
That it can follow the flight of song?
 
Long, Long afterward, in an oak
I found the arrow, still unbroke;
And the song from beginning to end,
I found again in the heart of a friend.”