#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=sqrt(2e9+5);
bool is_[N];
int su[N],tot;
int n;
int cnt; 
int pow(int x,int p,int mod){
	int book=x,an=1;
	while(p){
		if(p&1){
			an*=book;
			an%=mod;
		}
		book*=x;
		book%=mod;
	  p>>=1;
	}
	return an;
}
vector<int>t;
signed main(){
	for(int i=2;i<=N;i++){
		if(is_[i])continue;
		su[++tot]=i;
		for(int j=i*2;j<=N;j+=i){
			is_[j]=1;
		}
	}
	while(cin>>n){
		t.clear();
		cnt++;
		if(n==0)return 0;
		int d=__gcd(n,(long long)8);
		long long r=9*n/d;
		int ou=r;
		if(__gcd((long long)10,r)!=1){
			printf("Case %ld: 0\n",cnt);
		}else{
			for(int i=1;i<=tot;i++){
				if(r%su[i]==0){
					ou=ou/su[i]*(su[i]-1);
					while(r%su[i]==0)r/=su[i];
				}
			}
			if(r!=1){
				ou=ou/r*(r-1);
			}
            r=9*n/d;
           // cout<<ou<<endl;
           for(int i=1;i<=sqrt(ou);i++){
           		if(ou%i==0)t.push_back(i);
           		if(i*i!=ou)t.push_back(ou/i);
		   }
		   sort(t.begin(),t.end());
		   for(int i=0;i<t.size();i++){
		   		if(pow((long long )10,t[i],r)==1){
		   			printf("Case %ld: %lld\n",cnt,t[i]);
                       break;
				}
		   }
		}
		
		
		
	}
	return 0;
}