UVA -10179

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>

using namespace std;

#define REP(i,n) for(__typeof(n) i=0; i<(n); i++)
#define FOR(i,a,b) for(__typeof(b) i=(a); i<=(b); i++)
#define RFOR(i,a,b) for(__typeof(b) i=(a); i>(b); i--)
#define RESET(t,value) memset((t), value, sizeof(t))
typedef long long int64;
typedef long double d64;
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define PI acos(-1.0)
#define INF (1<<30)
#define eps 1e-8
#define pb push_back
#define ppb pop_back
#define pii pair<double,double>
#define G struct node

template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template< class T > void setmax(T &a, T b) { if(a < b) a = b; }
template< class T > void setmin(T &a, T b) { if(b < a) a = b; }

int GCD(int a, int b){return (b == 0 ? a : GCD(b, a % b));}
int LCM(int a, int b){ return (a * (b/ GCD(a, b))); }
int ABS(int a) {return ((a >= 0) ? a : -a); }

vector < int > pset;
void initSet(int _size){ pset.resize(_size); FOR(i,0,_size-1) pset[i]=i;}
int findSet(int i){return (pset[i]== i)?i: (pset[i] = findSet(pset[i]));}
void unionSet(int i,int j){ pset[findSet(i)]=findSet(j);}
bool isSameSet(int i,int j){ return findSet(i)==findSet(j);}

#define Max 1000000000
long long status[(Max/32)+2];
vector <long long> primeList, temp;
vector<long long>::iterator k;

set <long long> primeFactor;
set<long long>::iterator it;

bool Check(long long N,long long pos){return (bool)(N & (1<<pos));}
long long Set(long long N,long long pos){ return N=N | (1<<pos);}

void RSieve(long long N)
{
     primeList.clear();
     long long i, j, sqrtN;
     sqrtN = long( sqrt( N ) );
     for( i = 3; i <= sqrtN; i += 2 )
     {
         if( Check(status[i>>5],i&31)==0)
         {
             for( j = i*i; j <= N; j += (i<<1) )
             {
                 status[j>>5]=Set(status[j>>5],j & 31)   ;
             }
         }
     }
     primeList.pb(2);
     for(i=3;i<=N;i+=2)
         if( Check(status[i>>5],i&31)== 0) primeList.pb(i);
}

void factors(long long n){
    primeFactor.clear();

        REP(i, temp.size()){
            long long p = temp[i];
            while(n % p == 0){
                n = n / p;
                primeFactor.insert(p);
            }
        }
}
int main()
{
    READ("input.txt");
    long long n;
    RSieve(999999999);
    while(cin>>n)
    {
        if(n == 0) return 0;
        for(k = primeList.begin(); *k <= n; k++) temp.pb(*k);
        factors(n);
        long long res = n;
        for(it = primeFactor.begin(); it != primeFactor.end();it++){
            res = ceil(res*(1- 1/ float(*it)));
        }
        cout<<res<<endl;
    }
    return 0;
}