#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll phi(ll n){//欧拉函数
	ll rea=n;
	for(ll i=2;i*i<=n;i++){
		if(n%i==0){
			rea=rea-rea/i;
			do
			n/=i;
			while(n%i==0);
		}
	}
	if(n>1)rea=rea-rea/n;
	return rea;
}
ll multi(ll a,ll b,ll k){//a*b%k  直接乘会爆
	ll ans=0;
	while(b){
		if(b&1){
			ans=(ans+a)%k;
		}
		a=(a<<1)%k;
		b=b>>1;
	}
	return ans;
}
ll quick(ll a,ll k,ll m){//快速幂
	ll ans=1;
	while(k){
		if(k&1){
			ans=multi(ans,a,m);
		}
		a=multi(a,a,m);
		k>>=1;
	}
	return ans;
}
int main(){
	ll l,cas=1;
	while(scanf("%lld",&l)&&l){
		ll m=9*l/__gcd(l,(ll)8);
		printf("Case %lld: ",cas++);
		if(__gcd((ll)10,m)!=1){//无解
			printf("0\n");
			continue;
		}
		ll i,x=phi(m);
		ll flag=0;
		for(i=1;i<=sqrt(x);i++){//先找1-sqrt(x)中的因子
			if(x%i==0){
				if(quick(10,i,m)==1){
					flag=1;
					printf("%lld\n",i);
					break;
				}
			}
		}
		if(!flag){
			for(i=sqrt(x);i>=2;i--){//找sqrt(x)-x的因子
				if(x%i==0){
					if(quick(10,x/i,m)==1){
						printf("%lld\n",x/i);
						break;
					}
				}
			}
		}
	}
	return 0;
}
/*乘以一个八分之九，变成99999……9的形式。这样的好处是99999……9（k个9）等于10k次幂-1。 
“1”考虑转换成模一，方便和欧拉靠近 
我们假设这个数是8*(10^x-1)/9
即 8*(10^x-1)/9=k*L,我们左右俩边除以gcd(8,L) 这个非常关键。

(10^x-1)*8/gcd(8,L)=k*9*L/gcd(8,L);

我们注意到  8/gcd(8,L) 与L/gcd(8,L) 肯定互质，因为8与L的最大公约数都约去了。

我们注意到8与9也是互质的，没有公共的质因子，那么8/gcd(8,L)与9*L/gcd(8,L)互质￥￥实质上，2和3无法产生最大公约数，那么2和3*5*7*9都无法产生，因为
最大公约数是右边分解因式分出来的，只要和左边分不出最大公约数，左右就不会产生新的最大公约数，就始终互质 

我们令 mod= 9*L/gcd (8,L)令10的x次幂有机会转换成零式，这样由于有1的存在就能转换成欧拉 

在上面的等式左右模mod ,刚刚我们证明了 8/gcd(8,L)与mod 互质，那么%mod 肯定不为0

所以我们得到了:
(10^x-1)%mod=0;

即 (10^x-1)=k*mod
10^x=k*mod+1
10^x=1 %mod

变形到这里，我们已经完成了推导，现在就是欧拉定理了

依次求符合条件的x，取出最小值。 

*/

浅谈快速乘 快速乘，顾名思义，是一种能在 O ( 1 ) O(1) O(1)时间内求出 a × b m o d p a\times b\ mod p a×b modp的算法

为什么需要用到快速乘呢，例如1e18乘1e18的积对1e9+7取模，而显然1e18乘1e18的值爆出了 l o n g l o n g long\ long long long的范围，怎么办呢？

可能有学过快速幂的同学知道，可以利用近似于快速幂的思想，把拆分指数用在拆分因数，在 l o g b logb logb的时间范围内将其拆分并求积，这样每次运算的值都不会超出 l o n g l o n g long\ long long long。

当然，缺点也很明显，那就是慢！我们称这种算法叫慢速乘。

那么快速乘有怎样实现呢？

首先，快速乘是利用了 l o n g d o u b l e long\ double long double舍弃低位且范围保留18位的特点，使我们可以利用 l o n g d o u b l e long\ double long double加上 C + + C++ C++的自动转换功能完成快速乘的运算。

#include <bits/stdc++.h>
using namespace std;long long a,b,p;
typedef long long LL;
inline LL ksc(LL a,LL b,LL p)//快速乘
{
    a%=p;b%=p;
    long long c=(long double)a*b/p;
    long long ans=a*b-c*p;
    if(ans<0) ans+=p;
    else if(ans>=p) ans-=p;
    return ans;
}
signed main()
{
	scanf("%lld%lld%lld",&a,&b,&p);
	printf("%lld",ksc(a,b,p));
}