Do you have spent some time to think and try to solve those unsolved problem after one ACM contest?
No? Oh, you must do this when you want to become a "Big Cattle".
Now you will find that this problem is so familiar:
The greatest common divisor GCD (a, b) of two positive integers a and b, sometimes written (a, b), is the largest divisor common to a and b. For example, (1, 2) =1, (12, 18) =6. (a, b) can be easily found by the Euclidean algorithm. Now I am considering a little more difficult problem:
Given an integer N, please count the number of the integers M (0<M<N) which satisfies (N,M)>1.
This is a simple version of problem “GCD” which you have done in a contest recently,so I name this problem “GCD Again”.If you cannot solve it still,please take a good think about your method of study.
Good Luck!

Input contains multiple test cases. Each test case contains an integers N (1<N<100000000). A test case containing 0 terminates the input and this test case is not to be processed.

For each integers N you should output the number of integers M in one line, and with one line of output for each line in input.

2
4
0

0
1

lcy

欧拉函数 ：公式：f(x)=x*(1-1/p1)*(1-1/p2)*(1-1/p3)....*(1-1/pn) pi都是x的质因子 

考查知识点：欧拉函数 

//考查知识点：欧拉函数 。。。
#include<stdio.h>
int urler(int n)
{
	int ans=n,i;
	int temp=1;
	for(i=2;i*i<=n;++i)//要是从2开始遍历到 n-1 容易tle 在此再次压缩 
	{
		if(n%i==0)
		{
			ans-=ans/i;//欧拉函数公式 f（x）=n*(1-1/p1)*(i-i/p2)...(1-1/pn); 
			while(n%i==0)// 
			n/=i; 
		}
	}
	if(n>1)//上面压缩了 i的取值范围，此处n！=1说明此时的n也是原来n的一个质因子 
	ans-=ans/n;
	return ans;
}
int main()
{
	int n;
	while(~scanf("%d",&n),n)
	{
		printf("%d\n",n-urler(n)-1);
	}
	return 0;
}