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. 

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;
// 欧拉函数
int euler(int n)
{
    int ans=1;
    int i;
    for(i=2;i*i <=n;i++)
    {
        if(n%i ==0)
        {

            ans*=i-1;
            n/=i;
            while(n%i ==0)
            {
                ans*=i;
                n/=i;
            }
        }
    }
    if(n!=1)     // 最后一个因子为n!=1,保存
        ans*=n-1;
    return ans;
}

int main()
{
    int n;
    while(scanf("%d",&n)&& n)
    {
        printf("%d\n", n-1 - euler(n));
    }
    return 0;
}