题意：

给一个L,求长度最小的全8数满足该数是L的倍数。

分析：

转化为求方程a^x==1modm。

之后就是各种数学论证了。

代码：

//poj 3696

//sep9

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

ll L;

ll factor[65536];

ll mul(ll x,ll y,ll p)

{

	ll ret=0;

	while(y){

		if(y&1)

			ret=(ret+x)%p;

		x=(x+x)%p;

		y>>=1;

	}

	return ret;

}

ll pow(ll x,ll n,ll m)

{

	ll ret=1;

	x%=m;

	while(n){

		if(n&1)

			ret=mul(ret,x,m);

		x=mul(x,x,m);

		n>>=1;

	}

	return ret;

}

ll euler(ll n)

{

	ll ret=n;

	for(ll i=2;i*i<=n;++i)

		if(n%i==0){

			ret=ret/i*(i-1);

			while(n%i==0)

				n/=i;

		}

	if(n>1)

		ret=ret/n*(n-1);

	return ret;

}

ll cal()

{

	ll m=L*9;

	for(int i=0;i<3;++i)

		if(m%2==0)

			m/=2;

		else

 			break;

	if(m%2==0||m%5==0)

		return 0;

	ll phi=euler(m);

	int idx=0;

	for(ll i=1;i*i<=phi;++i)

		if(phi%i==0)

			factor[idx++]=i,factor[idx++]=phi/i;

	sort(factor,factor+idx);

	for(int i=0;i<idx;++i)

		if(pow(10,factor[i],m)==1)

			return factor[i];

}

int main()

{

	int cases=0;

	while(scanf("%I64d",&L)==1&&L){

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

		printf("%I64d\n",cal());

	}

	return 0;

}