#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
using namespace std;
typedef long long LL;
const int N = 1000000;
bool p[N]; ///为false代表是素数
int idx[N];
void init(){
    memset(p,false,sizeof(p));
    int id = 1;
    for(int i=2;i<N;i++){
        if(!p[i]){
            idx[i] = id++;
            for(LL j=(LL)i*i;j<N;j+=i){
                p[j] = true;
            }
        }
    }
}
int getMax(int n){
    int Max = -1;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            while(n%i==0){
                n/=i;
            }
            Max = max(i,Max);
        }
    }
    if(n>1) Max = max(Max,n);
    return Max;
}
int main()
{
    init();
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==1) printf("0\n");
        else{
            int Max = getMax(n);
            printf("%d\n",idx[Max]);
        }
    }
}