**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**

123456

7654321

0

**Sample Output**

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.”`

` `