A fraction mn is basic if 0 ≤ m < n and it is irreducible if gcd(m, n) = 1. Given a positive integer n, in this problem you are required to find out the number of irreducible basic fractions with denominator n. For example, the set of all basic fractions with denominator 12, before reduction to lowest terms, is Reduction yields 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10, 11 12 12 12 12 12 12 12 12 12 12 12 12 0 , 1 ,1,1,1, 5 ,1, 7 ,2,3,5,11 12 12 6 4 3 12 2 12 3 4 6 12 Hence there are only the following 4 irreducible basic fractions with denominator 12 0 , 5 , 7 , 11 12 12 12 12 Input Each line of the input contains a positive integer n (< 1000000000) and the input terminates with a value 0 for n (do not process this terminating value). Output For each n in the input print a line containing the number of irreducible basic fractions with denominator n. Sample Input 12 123456 7654321 0 Sample Output 4 41088 7251444