这里面的一个转换的小技巧很重要，把888...8转换成(10^x-1)/9*8。神来之笔，佩服。
这样有(10^x-1)/9*8=L*p得10^x-1=L*p*9/8，设m=9*L/gcd(L,8)。这一步如何想到的呢？其实是为了使m与10互质而做的。因为这样必有m*p1=10^x-1。使得同余方程
10^x=1 mod m，相信到了这一步，都知道用欧拉定理了。于是只需求出phi(m)，枚举其因子，使得同余方程成立即可
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define LL __int64
using namespace std;LL gcd(LL a,LL b){if(b==0) return a;return gcd(b,a%b);
}
LL fac[10000]; int cnt;
LL Euler(LL m){LL res=m;LL k=(LL)sqrt((double)m);for(LL i=2;i<=k;i++){if(m%i==0){res=res-res/i;while(m%i==0)m/=i;}}if(m>1)res=res-res/m;return res;
}LL multi(LL a,LL b,LL m){LL ret=0;while(b>0){if(b&1) ret=(ret+a)%m;b>>=1;a=(a<<1)%m;}return ret;
}LL quick(LL a,LL k,LL m){LL ans=1;while(k){if(k&1)ans=multi(ans,a,m);k=(k>>1);a=multi(a,a,m);}return ans;
}int main(){LL l; int kase=0; while(scanf("%I64d",&l),l){if(l%16==0||l%5==0) {printf("Case %d: 0\n",++kase);continue;}cnt=0;LL m=l*9/gcd(l,(LL)8);LL phi=Euler(m);LL ans;LL k=(LL)sqrt((double)phi);for(LL i=1;i<=k;i++){if(phi%i==0){fac[cnt++]=i;fac[cnt++]=phi/i;}}sort(fac,fac+cnt);for(int i=0;i<cnt;i++){ans=quick((LL)10,fac[i],m);if(ans==1){printf("Case %d: %I64d\n",++kase,fac[i]);break;}}}return 0;
}
