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

• 1999999973 (2187) liyuanlong 2008-11-04 21:29:21