#include <stdlib.h>#include <string.h>#include <stdio.h>#include <ctype.h>#include <math.h>#include <stack>#include <queue>#include <map>#include <set>#include <vector>#include <iostream>#include <algorithm>using namespace std;#define ll long long#define ls rt<<1#define rs ls1#define lson l,mid,ls#define rson mid+1,r,rs#define middle (l+r)>>1#define eps (1e-9)#define type int#define clr_all(x,c) memset(x,c,sizeof(x))#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1))#define MOD 1000000007#define inf 0x3f3f3f3f#define pi acos(-1.0)#define M 1000000int p[M],a[M],m;void Init(){int i,j;for(i=0;i<M;i++)a[i]=1;a[0]=0;a[1]=0;for(i=2;i<M;i++){if(a[i]==1)for(j=i*2;j<M;j+=i)a[j]=0;}j=0; for(i=2;i<M;i++)if(a[i]==1)p[j++]=i;m=j;}int main(){ int n,i,j,cnt; Init(); while(scanf("%d",&n)&&n){cnt=n; i=0; j=n;for(i=0;i<m;i++){if(j%p[i]==0){cnt/=p[i];cnt*=(p[i]-1);while(j%p[i]==0)j/=p[i];if(j==1)break;}}if(j!=1){cnt/=j;cnt*=(j-1);}printf("%dn",cnt);} return 0;}
