/*

    个人感觉很神的一道题目。

    如果有解的话，会有一个p满足：(10^x-1)/9*8=L*p

                              => 10^x-1=9*L*p/8

    设m=9*L/gcd(L,8)

    则存在p1使得 10^x-1=m*p1

              => 10^x=1(mod m)

    根据欧拉定理 10^φ(m)=1(mod m)

    所以x一定是φ(m)的因数（这好像是某个定理）。

*/

#include<iostream>

#include<cstdio>

#define lon long long

#define N 400010

#ifdef unix

#define LL "%lld"

#else

#define LL "%I64d"

#endif

using namespace std;

int prime[N],f[N],num,qlen;

lon q[N];

void get_prime(){

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

        if(!f[i]) prime[++num]=i;

        for(int j=;j<=num;j++){

            if(i*prime[j]>=N) break;

            f[i*prime[j]]=;

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

        }

    }

}

lon gcd(lon a,lon b){

    if(!b) return a;

    return gcd(b,a%b);

}

lon euler(lon x){

    lon res=x;

    for(lon i=;i*i<=x;i++)

        if(x%i==){

            res-=res/i;

            while(x%i==) x/=i;

        }

    if(x>) res-=res/x;

    return res;

}

void get_q(lon n){

    qlen=;

    for(int i=;i<=num&&n>;i++){

        while(n%(lon)prime[i]==){

            n/=prime[i];

            q[++qlen]=prime[i];

        }

    }

    if(n>) q[++qlen]=n;

}

lon mul(lon a,lon b,lon mod){

    lon base=a,r=;

    while(b){

        if(b&) r+=base;r%=mod;

        base+=base;base%=mod;

        b>>=;

    }

    return r;

}

lon poww(lon a,lon b,lon mod){

    lon base=a,r=;

    while(b){

        if(b&) r=mul(r,base,mod);

        base=mul(base,base,mod);

        b>>=;

    }

    return r;

}

int main(){

    int cas=;lon L;get_prime();

    while(scanf(LL,&L)&&L){

        lon m=*L/gcd(L,);

        if(gcd(m,)>){

            printf("Case %d: 0\n",++cas);

            continue;

        }

        lon x=euler(m);get_q(x);

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

            if(poww(,x/q[i],m)==){

                x/=q[i];

            }

        }

        printf("Case %d: ",++cas);

        printf(LL,x);printf("\n");

    }

    return ;

}