#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 = ;

bool p[N]; ///为false代表是素数

int idx[N];

void init(){

    memset(p,false,sizeof(p));

    int id = ;

    for(int i=;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 = -;

    for(int i=;i*i<=n;i++){

        if(n%i==){

            while(n%i==){

                n/=i;

            }

            Max = max(i,Max);

        }

    }

    if(n>) Max = max(Max,n);

    return Max;

}

int main()

{

    init();

    int n;

    while(scanf("%d",&n)!=EOF){

        if(n==) printf("0\n");

        else{

            int Max = getMax(n);

            printf("%d\n",idx[Max]);

        }

    }

}

/*求第n个质数*/

#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 = ;

int n,m;

int p[];//存储素数

bool a[N];

//O(n) 素数筛

void init() {

    memset(a,false,sizeof(a));//初始全部为素数

    int num=;

    for(int i=;i<N;++i) {

        if(!a[i]) p[num++]=i;

        for(int j=;(j<num&&i*p[j]<N);++j) {

            a[i*p[j]]=;

            if(i%p[j] == ) break;

        }

    }

}

int main(){

    init();

    int n;

    int k = ;

    while(scanf("%d",&n)!=EOF){

       if(n==) break;

       printf("Case %d: %d\n",++k,p[n-]);

    }

}