考虑x个8的整数可以表示为$\dfrac{10^x-1}{9}\times 8$，于是这个问题相当于求解最小的x满足：
$$ \dfrac{10^x-1}{9}\times 8 \equiv 0\ (mod\ L) $$
整理下就是：
$$ 8(10^x-1) \equiv 0\ (mod\ 9L) $$
为了满足条件，8的存在可以化简一下模数，直接放进去考虑，即：
$$ 10^x-1 \equiv 0\ (mod\ \dfrac{9L}{\gcd(L, 8)}) $$
也就是：
$$ 10^x \equiv 1\ (mod\ \dfrac{9L}{\gcd(L, 8)}) $$
令$p=\dfrac{9L}{\gcd(L, 8)}$，考虑$x$与$p$不一定互质，所以应用欧拉定理，得到一个可行解：令$x=\phi(p)$
$$ 10^{\phi(p)} \equiv 1\ (mod\ p) $$
由于$\phi(p)$不一定是满足条件的最小自然数，但是可以证明满足上式的$x$一定是$\phi(p)$的因子，于是我们枚举$\phi(p)$的因子判断是否满足条件即可。

C++ 代码

#include<bits/stdc++.h>

using namespace std;
using LL = long long;

LL mul(LL x, LL n, LL mod) {
  LL ret = 1;
  while (n) {
    if (n & 1) ret = ret * x % mod;
    n >>= 1;
    x = x * x % mod;
  }
  return ret;
}

LL phi(LL x) {
  LL ret = x;
  for (LL i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      ret = ret / i * (i - 1);
      while (x % i == 0) x /= i;
    }
  }
  if (x > 1) ret = ret / x * (x - 1);
  return ret;
}

signed main() {
  // freopen("in", "r", stdin);
  LL L;
  for (int _ = 1; cin >> L && L; _++) {
    LL mod = L / __gcd(8LL, L) * 9LL;
    LL p = phi(mod), ret = 1E18;
    for (LL x = 1; x * x <= p; x++) {
      if (p % x != 0) continue;
      if (mul(10, x, mod) == 1) ret = min(ret, x);
      if (mul(10, p / x, mod) == 1) ret = min(ret, p / x);
    }
    printf("Case %d: ", _);
    printf("%lld\n", ret == 1E18 ? 0 : ret);
  }
  return 0;
}