Description

Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz.

Input

There are several test cases. For each test case, standard input contains a line with n <= 1,000,000,000. A line containing 0 follows the last case.

Output

For each test case there should be single line of output answering the question posed above.

Sample Input

7

12

0

Sample Output

6

4

解题思路：欧拉函数：求不大于n且与n互质的数的个数。

AC代码：

1 #include
     
       2 using namespace std; 3 int Euler(int x){ 4     int r=x; 5     for(int i=2;i*i<=x;i++){
    //由于任何一个合数都至少有一个不大于根号x的质因子，所以只需遍历到根号x即可 6         if(x%i==0){ 7             r=r/i*(i-1);//欧拉函数的通式，先除后乘，避免数据溢出 8             while(x%i==0)x/=i;//消除x中所有质因子i，直到不能被i整除 9         }10     }11     if(x>1)r=r/x*(x-1);//如果x大于1，说明还有一个质因子没有除掉12     return r;//返回个数13 }14 int main(){15     int n;16     while(cin>>n&&n)17         cout<
      
       <