> #include <iostream>
> using namespace std;
> 
> const int MAX = 31624 + 10; //1000000000的平方根
> bool nprime[MAX];
> int prime[MAX];
> int main()
> {
> 	memset(nprime, 0, sizeof(bool)*MAX);
> 	int i, j;
> 	for(i = 2; i < MAX/2; i ++)
> 	{
> 		for(j = i*i; j < MAX; j += i)
>               nprime[j] = true;
> 	}
> 	int c = 0;
> 	for(i = 2; i < MAX; i ++)
> 		if(!nprime[i])
> 		{		
> 		    prime[c ++] = i;
> 		}
> 	int n;
> 	while(cin >> n && n)
> 	{
> 		int ans = n;
> 		for(i = 0; i < c; i ++)
> 		 {
> 			if(n%prime[i] == 0)
> 			{
> 				ans /= prime[i];
> 				ans *= prime[i] - 1;		
> 			}
> 		 }
> 		 if(ans == n)
> 			 ans = n - 1;
> 		 cout << ans << endl;
> 	}
> 	return 0; 
> }