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₁, i₂, i₃,... in which the value of i_n 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 < 2³¹. 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

Sample Output

FAU Local Contest 2004-07-10
Author: Tilmann Spiegelhauer