#10179Irreducible Basic Fractions

A fraction m / n is basic if 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.”

Source: http://uva.onlinejudge.org/external/101/10179.htmlKeyword:number theory