#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int M=1e4;
struct mat
{
    int a[2][2];
    mat friend operator*(const mat &u,const mat &v)
    {
        mat C;memset(C.a,0,sizeof(C.a));
        for(int k=0;k<2;k++)
        {
            for(int i=0;i<2;i++)
            {
                for(int j=0;j<2;j++)
                {
                    (C.a[i][j]+=u.a[i][k]*v.a[k][j])%=M;
                }
            }
        }
        return C;
  } 
};
mat pow(mat a,ll n)
{
    mat b;b.a[0][0]=b.a[1][1]=1;
    b.a[0][1]=b.a[1][0]=0;
    while(n)
    {
        if(n&1) b=b*a;
        a=a*a;
        n>>=1;
    }
    return b;
}
int n;
const int P=1e3;
void solve()
{
    scanf("%d",&n);
    mat a;
    a.a[0][0]=a.a[1][1]=3;
    a.a[1][0]=1;a.a[0][1]=5;
    a=pow(a,n);
    printf("%03d\n",(a.a[0][0]*2+P-1)%P);
}
int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    int tc;scanf("%d",&tc);
    for(int tt=1;tt<=tc;tt++)
    {
        printf("Case #%d: ",tt);
        solve();
    }
    return 0;
}