最幸运的数字

思路：
设最终数除以L为x， y为最终数字除以8，那就是xL - 8y = 0；
分析：
上述的思路是错误的，因为从x倒出来就是y，也就是恒等式，只是强行凑出一个“像”扩欧的东西而已
分析如下：
这题难搞的就是那个88…8，这个东西，因为他属于是那种看起来就不符合数学认知规律而符合我们生活中尝试认知规律的数字，所以对他进行转化
8…8 = 8 * 1…1 = 8 * $\frac{9…9}{9}$ = 8 * $\frac{10^x - 1}{9}$
也就是我们需要找到一个x使得L整除8 * $\frac{10^x - 1}{9}$
移项一下
9L | 8 * $10^x - 1$
因为这个式子在结论上是成立的，但是9和8又是互质的，所以L和8必定不是互质的
令d=(L,8),然后让等式左边消去d，右边消去8，这一步是去掉杂项
$\frac{9L}{d}$ | $10^x - 1$
从此等式左边是常数，用C代替一下
C | $10^x - 1$
也就是：
$10^x$ $\equiv$ 1(mod C)
至此扩欧的只用条件也构成了，也符合使用欧拉函数的条件（$a^{\phi{n}} \equiv 1$, 当且仅当(a, n) = 1）
但是这题说是要找最小的那个解，欧拉定理可能并不满足条件，因为求出来的仅是“一组”解
所以，当$\phi{C}$是一组解并不是最小的一组解时，最小的一组解就是$\phi{C}$的某个约数（反证法证明）
然后再用之前的方法遍历约数求解即可
代码：

//wengyan17的init
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'
#define cerr(x) std::cerr << (#x) << " is " << (x) << '\n'
#define IOS std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
#define PII pair<int, int>
#define pdd pair<double,double>
#define LL long long
#define rep(i,a,b) for (int i = a; i <= b; i ++)
#define per(i,b,a) for (int i = b; i >= a; i --)

const double CLOCKS_PER_SECOND = ((clock_t)1000);
const double CLOCKS_PER_MILLISECOND = ((clock_t)1);
const int N = 2e5 + 10, mod = 1e9 + 7;
//#define x first
//#define y second


int L;

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);
        a = qmul(a, a, b);
        k >>= 1;
    }
    return res;
}

int get_euler(int C) {
    LL res = C;
    for (int 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;
}

signed main()
{
    //IOS;
    int T = 1;
    while (cin >> L, L) {
        int d = 1;
        while (L % (2 * d) == 0 && 2 * d <= 8) d *= 2;

        LL C = 9 * L / d;
        LL phi = get_euler(C);

        LL res = 1e18;
        if (C % 2 == 0 || C % 5 == 0) {
            printf("Case %lld: %lld\n", T ++, 0);
        } else {
            for (int x = 1; x * x <= phi; x ++) {
                if (phi % x == 0) {
                    if (qmi(10, x, C) == 1) {
                        res = min(res, x);
                    }
                    if (qmi(10, phi / x, C) == 1) {
                        res = min(res, phi / x);
                    }
                }
            }
            printf("Case %lld: %lld\n", T ++, res);
        }
    }
    return 0;
}