import math

def gcd(a, b):
    if a > b:
        a, b, = b, a

    while a:
        a, b = b % a, a
    return b


def pow_mod(a, k, p):
    t = []
    pow_val = 1             # 2的次幂数, 初始是2^0 = 1
    a_pow = a % p           # a^(2 ^ i)的数值, 初始是a^(2^0) = a
    while pow_val <= k:
        t.append(a_pow)
        a_pow = (a_pow*a_pow) % p
        pow_val <<= 1

    ans = 1
    for i in range(len(t)):
        if k & 1:
            ans = (ans * t[i]) % p
        k >>= 1
    return ans

def get_eular(val):
    ans = val
    for i in range(2, int(math.sqrt(val)) + 1):
        if val % i == 0:
            while val % i == 0:
                val //= i

            ans = ans // i * (i - 1)

        if val == 1:
            break

    # 特判最后可能剩下的大于sqrt(val)的最大的质因子
    if val != 1:
        ans = ans // val * (val - 1)
    return ans

# 分解质因数函数，返回元组数组[ (质因子1, 次幂1)， (质因子2, 次幂2)， (质因子3, 次幂3) ...... ]
# 质因子的数值升序排列
def devide_prime(val):
    ans = []
    for i in range(2, int(math.sqrt(val)) + 1):
        if val % i == 0:
            cnt = 0
            while val % i == 0:
                val //= i
                cnt += 1

            ans.append((i, cnt))

        if val == 1:
            break

    # 特判最后可能剩下的大于sqrt(val)的最大的质因子
    if val != 1:
        ans.append((val, 1))

    return ans

# 获取所有约数的函数
def get_approximate_numbers(val):
    ans = []
    primes = devide_prime(val)

    up_bound = int(math.sqrt(val))
    def dfs(idx, prev_val):
        if prev_val > up_bound:
            return

        if idx >= len(primes):
            ans.append(prev_val)
            if val // prev_val != prev_val:
                ans.append(val // prev_val)

            return

        base = None
        for pow_val in range(primes[idx][1]+1):
            if pow_val == 0:
                base = 1
            else:
                base *= primes[idx][0]

            dfs(idx+1, prev_val * base)
    dfs(0, 1)

    ans.sort()
    return ans


case_idx = 1
while True:
    L = int(input())
    if L == 0:
        break

    d = gcd(L, 8)
    C = 9 * L // d
    eular_val = get_eular(C)
    app_vals = get_approximate_numbers(eular_val)


    if gcd(10, C) != 1:
        # 无解
        print(f'Case {case_idx}: 0')
    else:
        ans = None
        for app_val in app_vals:
            if pow_mod(10, app_val, C) == 1:
                ans = app_val
                break
        print(f'Case {case_idx}: {ans}')

    case_idx += 1