> #include"stdio.h"
> #include"string.h"
> #include"math.h"
> 
> bool hash[44723]={0},flag,have[1000];
> int prime[5000],top,icase=0;
> __int64 f[1000],top1,w[1000],top2,q,p;
> __int64 gcd(__int64 a,int b)
> {
> 	if(a%8==0)return 8;
> 	if(a%4==0)return 4;
> 	if(a%2==0)return 2;
> 	return 1;
> }
> 
> unsigned __int64 pro(unsigned __int64 x,unsigned __int64 y,unsigned __int64 n)
> {
> 	unsigned __int64 ret,tmp;
> 	int i;
> 	if(n<=1000000000)
> 		return (x*y)%n;
> 	else if(x<=10000000||y<=10000000)
> 	return (x*y)%n;
> 	else
> 	{
> 		tmp=(y/100*x)%n;
> 		ret=0;
> 		for(i=0;i<100;i++)
> 			ret=(ret+tmp)%n;
> 		tmp=y%100;
> 		ret=(ret+(tmp*x)%n)%n;
> 	}
> 
> 	return ret;
> }
> 
> __int64 phi(__int64 res)
> {
> 	int i,j,k;
> 	__int64 anw=res;
> 	
> 	for(i=0;i<top;i++)
> 	if(res%prime[i]==0)
> 	{
> 		anw=anw*(prime[i]-1)/prime[i];
> 		while(res%prime[i]==0)
> 		res=res/prime[i];
> 		
> 	}
> 	if(res!=1)
> 	anw=anw*(res-1)/res;
> 	
> 	return anw;
> }
> 
> 
> 
> __int64 mod(__int64 a,__int64 b,__int64 m)
> {
> 	__int64 k,res;
> 	k=b;res=1;
> 	while(k>0)
> 	{
> 		if(k%2==1)
> 		res=pro(res,a,m);	
> 	    a=pro(a,a,m);
> 		k=k>>1;
> 	}
> 	return res;
> }	
> 
> 
> 
> void solve()
> {
> 	int i,j,k,t;
> 	
> 	t=sqrt((double)p)+1;
> 	top2=0;
> 	for(i=1;i<=t;i++)
> 	if(p%i==0)
> 	{
> 		if(mod(10,i,q)==1)
> 		w[top2++]=i;
> 		if(mod(10,p/i,q)==1)
> 		w[top2++]=p/i;
> 	}
> }
> 
> int main()
> {
> 	int i,j,k,n,m,l;
> 	__int64 max;
> 	
> 	for(i=2;i<=212;i++)
> 	if(hash[i]==0)
> 	{
> 		for(j=2;i*j<=44722;j++)
> 		hash[i*j]=1;
> 	}
> 	
> 	for(i=2;i<=44722;i++)
> 	if(hash[i]==0)
> 	{
> 		prime[top++]=i;
> 	}
> 	
> 	while(scanf("%d",&l)&&l)
> 	{
> 		icase++;
> 		if(l%5==0||l%16==0)
> 		{
> 			printf("Case %d: 0\n",icase);
> 			continue;
> 		}
> 		
> 		q=(__int64)l*9;
> 		i=gcd(l,8);
> 		q=q/i;
> 		p=phi(q);
> 		flag=1;
> 		top2=0;
> 		solve();
> 		max=w[0];
> 		for(i=1;i<top2;i++)
> 			if(max>w[i])max=w[i];
> 		if(top2==0)
> 		    printf("Case %d: 0\n",icase);
> 		else
> 			printf("Case %d: %I64d\n",icase,max);
> 		
> 	}
> 	return 1;
> }
>