/*
 * if you are interested in the reference code here,
 * see https://g...content-available-to-author-only...b.com/georeth/OJLIBS for more information
 *
 * Solution Author : Georeth Chow <georeth2010@gmail.com>
 */
#include <cstdio>
#include <cmath>
#include <cstring>      // memset
#include <cstdlib>      // malloc
#include <cstdint>      // int64_t
#include <cinttypes>    // PRId64 SCNd64
#include <numeric>      // accumulate, partial_sum, inner_product, iota, adjacent_difference
#include <vector>
#include <map>
#include <set>
#include <tuple>        // pair, tuple
#include <iostream>
#include <algorithm>
#include <utility>
#include <iterator>
template <typename It>
struct iter_range : std::pair<It, It> {
    typedef std::pair<It, It> base_t;
    using base_t::base_t;
    It begin() { return base_t::first; }
    It end() { return base_t::second; }
};
template <typename It>
iter_range<std::reverse_iterator<It>> rev(const iter_range<It> &origin) {
    using rev_t = std::reverse_iterator<It>;
    return {rev_t(origin.second), rev_t(origin.first)};
}
template <typename Int = int>
struct int_iter {
    Int i;
    explicit int_iter(Int i = 0) : i(i) { }
    Int operator*() const { return i; }
    int_iter &operator++() { ++i; return *this; }
    int_iter &operator--() { --i; return *this; }
    int_iter operator+(Int step) const { return int_iter(i + step); }
    int_iter operator-(Int step) const { return int_iter(i - step); }
    Int operator-(const int_iter &that) const { return i - that.i; }
    int_iter &operator+=(Int step) { i += step; return *this; }
    int_iter &operator-=(Int step) { i -= step; return *this; }
    bool operator==(const int_iter &that) const { return  i == that.i; }
    bool operator!=(const int_iter &that) const { return !(*this == that); }
    Int operator[](Int n) { return i + n; }
    typedef Int difference_type;
    typedef Int value_type;
    typedef Int *pointer;
    typedef Int reference; // not a int container, never reference to int
    typedef std::random_access_iterator_tag iterator_category;
};
typedef iter_range<int_iter<>> range_t;
range_t range(int b, int e) { return {int_iter<>(b), int_iter<>(e > b ? e : b)}; }
range_t range(int n) { return range(0, n); }
range_t nrange(int n) { return range(1, n+1); }
range_t inrange(int b, int e) { return range(b, e + 1); }
using namespace std;    // use as solution header. name polution is fine.
#ifdef LOCAL_JUDGE
#  define pr_debug(...) fprintf(stderr, __VA_ARGS__)
#else
#  define pr_debug(...)
#endif
template <typename T>
bool chmax(T &m, const T &v) { if (v > m) return m = v, true; return false; }
template <typename T>
bool chmin(T &m, const T &v) { if (v < m) return m = v, true; return false; }
void fio() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}
#include <boost/multiprecision/gmp.hpp>
using namespace boost::multiprecision;
/* =====  SOLUTION START  ===== */
typedef int_iter<int64_t> ll_it;
int64_t N;
int64_t ValidB;
mpz_int all_ones(int nd, int64_t B) {
    mpz_int p(1);
    mpz_int ans = 0;
    while (nd--) {
        ans += p;
        p *= B;
    }
    return ans;
}
void valid_digit(int nd) {
    lower_bound(ll_it(2LL), ll_it(numeric_limits<int64_t>::max()), N, [=](int64_t B, int64_t N) {
                mpz_int num = all_ones(nd, B);
                if (num == N) chmin(ValidB, B);
                return all_ones(nd, B) < N;
            });
}
void solve() {
    cin >> N;
    ValidB = N - 1;
    for (int i : nrange(64))
        valid_digit(i);
    cout << ValidB << endl;
}
int main() {
    int T;
    cin >> T;
    for (int i : nrange(T)) {
        cout << "Case #" << i << ": ";
        solve();
    }
    return 0;
}