Relatives

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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <set>
using namespace std;
typedef long long LL ;
int eulerint n){ //返回eulern)
     int res=n,a=n;
     forint i=2;i*i<=a;i++){
         ifa%i==0){
             res=res/i*i-1);//先进行除法是为了防止中间数据的溢出
             whilea%i==0) a/=i;
         }
     }
     ifa>1) res=res/a*a-1);
     return res;
}

int main ){
int x;
while~scanf"%d",&x)&&x){
    printf"%d
",eulerx));
}
return 0;
}