The fraction m/n is called regular irreducible, if 0<m<n and GCD(m,n)=1. Find the number of regular irreducible fractions with the denominator n.
Each line is a separate test case that contains one integer n (n<109). The last line contains 0 and is not processed. The number of test cases is no more than 100.
For each value of n print in a separate line the answer to the problem.