// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include <bits/stdc++.h>
// #define int long long
#define i64 long long
#define pii pair <int, int> 
using namespace std;
char White;
inline int read(void) {
    int x=0,sgn=1; char ch=getchar();
    while(ch<48||57<ch) {if(ch==45)sgn=0;ch=getchar();}
    while(47<ch&&ch<58) {x=x*10+ch-48;   ch=getchar();}
    White=ch; return sgn? x:-x;
}
void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int Lim=5000000;
short res[11][Lim+2],*vis,k;
int b[12],cntb;
inline int trans(int x) {
    if(x>=k) return (x%k)*(x%k)+trans(x/k);
    return x*x;
}
inline int dfs(int x) {
    if(!vis[x]) {
        vis[x]=3;
        return vis[x]=dfs(trans(x));
    }
    if(vis[x]==3) return vis[x]=2;
    return vis[x];
}
signed main() {
    for(int base=2; base<=10; ++base) {
        vis=res[base]; k=base;
        vis[1]=1; const int L=base*base*base;
        for(int i=2; i<=L; ++i) dfs(i);
        for(int i=L+1; i<=Lim; ++i) vis[i]=vis[trans(i)];
    }
    fprintf(stderr,"%.4lf\n",1.0*clock()/CLOCKS_PER_SEC);
    int T=read();
    for(int t=1; t<=T; ++t) {
        b[cntb=1]=read();
        while(White!='\n') b[++cntb]=read();
        bool gg=1;
        for(int i=2; i<=Lim; ++i) if(res[b[cntb]][i]==1) {
            gg=0;
            for(int u=1; u<cntb; ++u) if(res[b[u]][i]==2) gg=1; 
            if(!gg) {
                printf("Case #%d: %d\n",t,i);
                break;
            }
        } 
        if(gg) printf("Case #%d: 11814485\n",t);
    }
    return 0;
}