# Azerbaijan Programming Olympiad - 2nd Stage preparation

# Number Theory

Mathematicians are a curious breed of people. Especially number theorists. They spend most of their time thinking about different properties of numbers. Albert Meyer, a number theorist, is trying to discover an interesting sequence of positive integers. He suspects the sequence `i`

, _{1}`i`

, _{2}`i`

,... _{3}`i`

which the value of _{n}`i`

is the number of numbers _{n}**m**, such that **1** ≤ **m** ≤ **n**, **gcd**(**m**, **n**) ≠ **1** and **gcd**(**m**, **n**) ≠ **m**, is very interesting. **gcd** is short for "greatest common divisor". He has turned to you, as you are an expert programmer and the calculations by hand are very tedious, to calculate a few numbers in this sequence.

#### Input

Each line contains one positive integer **n** (**0** < **n** < `2`

).^{31}

#### Output

For each number **n** print the amount of numbers **m**, such that **1** ≤ **m** ≤ **n**, **gcd**(**m**, **n**) ≠ **1** and **gcd**(**m**, **n**) ≠ **m**.

1 2 6 2147000000

0 0 1 1340599805