#include <iostream>

using namespace std;
typedef long long LL;

int check(LL n, LL b, int i)
{
    LL res = 0;
    for (int k = 0; k < i; k++)
    {
        if (res > (n - 1) / b) return 1; //使用除法，防止数据溢出, res * b + 1会溢出
        res = res * b + 1;
    }
    if (res == n) return 0;

    return -1;
}

int main()
{
   int T;
   cin >> T;

   //整数n能不能用某一个进制b表示成连续i个1的形式
   //从大到小枚举i
   //二分出进制b，满足进制数大于b的进制表示下，n小于连续i个1，小于b的进制n大于连续i个1表示的数
   //最终答案就是n等于连续i个1表示的数
   for (int t = 1; t <= T; t++)
   {
        LL n;
        cin >> n;

        for (int i = 63; i > 0; i--) //二分枚举
        {
            LL l = 2, r = n;
            while (l < r)
            {
                LL mid = (l + r) / 2;
                if (check(n, mid, i) >= 0) r = mid;
                else l = mid + 1;
            }
            if (check(n, l, i) == 0) //整数n可以在l进制下表示i位1.
            {
                printf("Case #%d: %lld\n", t, l);
                break;
            }
        }
   }

    return 0;
}