#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define si(X) scanf("%d", &(X))
#define sll(X) scanf("%lld",&(X))

const ll mod = 1e18+7;
ll expo(ll base , ll pow , ll n){
    ll ans = 1;
    while(pow!=0){
        if(base > n || base <= 0){
            return -1;
        }
        if(pow&1==1){
        	if(ans > n/base) return -1;
            ans = ans*base;
            if(ans > n|| ans <= 0){
                return -1;
            }
            //ans = ans%mod;
        }
        if(base > n/base) base = mod;
        else
        	base *= base;
       // base%=mod;
        pow/=2;

    }
    return ans;
}

/* -------Template ends here-------- */

const int M = 100001;


int fits(ll base , int dig , ll n){
    for(int i = dig - 1 ; i>=0 ; i--){
        ll temp = expo(base , i , n);
        if(temp == -1)
            return -1;
        n -= temp;
        if(n<0)
            return -1;
    }
    if(n == 0)
        return 0;
    return 1;
}
int main(){
    
	int t;
	si(t);

	for(int alp = 1;alp<=t;alp++){
		
        ll n;
        sll(n);
        ll ans = n - 1;
        int dig = 1;

        for(int digits = 70 ; digits >= 2 ; digits--){
            ll lo = 2 , hi = n - 1;
            int o = 0;
            while(lo <= hi){
                ll mid = (lo + hi + 1)/2;
                int num = fits(mid , digits , n);
                if(num == 0){
                    ans = mid;
                    o++;
                    break;
                }
                else if(num == 1){                     // this base is small
                    lo = mid + 1;
                }
                else{                                // this base is large
                    hi = mid - 1;
                }
            }
            if(o){
                break;
            }
        }





		cout<<"Case #"<<alp<<": "<<ans<<endl;

	}

}