8是中国的幸运数字，如果一个数字的每一位都由8构成则该数字被称作是幸运数字。

现在给定一个正整数L，请问至少多少个8连在一起组成的正整数（即最小幸运数字）是L的倍数。

输入格式
输入包含多组测试用例。

每组测试用例占一行，包含一个整数L。

当输入用例L=0时，表示输入终止，该用例无需处理。

输出格式
每组测试用例输出结果占一行。

结果为“Case 1: ”+一个整数N，N代表满足条件的最小幸运数字的位数。

如果满足条件的幸运数字不存在，则N=0。

数据范围
1≤L≤2∗109
输入样例：

8
11
16
0

输出样例：

Case 1: 1
Case 2: 2
Case 3: 0

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qmul(ll a,ll k,ll b)
{
    ll res=0;
    while(k)
    {
        if(k&1)res=(res+a)%b;
        a=(a+a)%b;
        k>>=1;
    }
    return res;
}
ll qmi(ll a,ll k,ll b)
{
    ll res=1;
    while(k)
    {
        if(k&1)res=qmul(res,a,b);  //因为C为10^10两个数相乘会爆long long 
        a=qmul(a,a,b);
        k>>=1;
    }
    return res;
}
ll get_euler(ll c)
{
    ll res=c;
    for(ll i=2;i<=c/i;i++)
        if(c%i==0)
        {
            while(c%i==0)c/=i;
            res=res/i*(i-1);
        }
    if(c>1)res=res/c*(c-1);
    return res;
}
int main()
{
    ll t=1;
    ll l;
    while(cin>>l,l)
    {
        ll d=1;
        while(l%(d*2)==0&&d*2<=8)d*=2;
        ll c=9*l/d;
        ll phi=get_euler(c);            //互质的数的个数;
        ll res=1e18;
        if(c%2==0||c%5==0)res=0;        //不互质则不存在; 
        else 
        {
            for(ll d=1;d<=phi/d;d++)
            {
                if(phi%d==0)
                {
                    if(qmi(10,d,c)==1)res=min(res,d);
                    if(qmi(10,phi/d,c)==1)res=min(res,phi/d);
                }
            }
        }
        printf("Case %d: %lld\n", t ++, res);
    }
}