A fraction m / n is basic if 0 <= m < n and it is irreducible if gcd(m, n) = 1. Given a(adsbygoogle = window.adsbygoogle || []).push({});

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

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# How it will be solved

**Physics Forums | Science Articles, Homework Help, Discussion**