e-olymp
Competitions

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