#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#define LL __int64

using namespace std;

LL gcd(LL a,LL b){

	if(b==0) return a;

	return gcd(b,a%b);

}

LL fac[10000]; int cnt;

LL Euler(LL m){

	LL res=m;

	LL k=(LL)sqrt((double)m);

	for(LL i=2;i<=k;i++){

		if(m%i==0){

			res=res-res/i;

			while(m%i==0)

			m/=i;

		}

	}

	if(m>1)

	res=res-res/m;

	return res;

}

LL multi(LL a,LL b,LL m){

    LL ret=0;

    while(b>0){

        if(b&1) ret=(ret+a)%m;

        b>>=1;

        a=(a<<1)%m;

    }

    return ret;

}

LL quick(LL a,LL k,LL m){

	LL ans=1;

	while(k){

		if(k&1)

		ans=multi(ans,a,m);

		k=(k>>1);

		a=multi(a,a,m);

	}

	return ans;

}

int main(){

	LL l; int kase=0;

	while(scanf("%I64d",&l),l){

		if(l%16==0||l%5==0) {

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

			continue;

		}

		cnt=0;

		LL m=l*9/gcd(l,(LL)8);

		LL phi=Euler(m);

		LL ans;

		LL k=(LL)sqrt((double)phi);

		for(LL i=1;i<=k;i++){

			if(phi%i==0){

				fac[cnt++]=i;

				fac[cnt++]=phi/i;

			}

		}

		sort(fac,fac+cnt);

		for(int i=0;i<cnt;i++){

			ans=quick((LL)10,fac[i],m);

			if(ans==1){

				printf("Case %d: %I64d\n",++kase,fac[i]);

				break;

			}

		}

	}

	return 0;

}