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, 1 ≤ m ≤ n, where 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 The input will consist of several positive integers 0 ≤ n ≤ 231. The input will be terminated by EOF. Output For each number output the number of numbers m, 1 ≤ m ≤ n, where gcd(m, n) ̸= 1 and gcd(m, n) ̸= m. Sample Input 1 2 6 2147000000 Sample Output 0 0 1 1340599805