 favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

# 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 `i1`, `i2`, `i3`,... `in` which the value of `in` is the number of numbers m, such that 1mn, 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 < `231`).

#### Output

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

Time limit 1 second
Memory limit 128 MiB
Input example #1
```1
2
6
2147000000
```
Output example #1
```0
0
1
1340599805
```