#include <iostream>

#include <cstdio>

#include <cstring>

#define mod %10056

using namespace std;

const int maxn = 1001;

int c[maxn+5][maxn+5], f[maxn+5];

void init(){

    for(int i = 0; i < maxn; i++)

        c[i][i] = 1, c[i][0] = 1;

    for(int i = 1; i < 1001; i++)

        for(int j = 1; j <= i; j++)

            c[i][j] = (c[i-1][j-1] + c[i-1][j]) mod;

}

void solve(){

    f[0] = 1, f[1] = 1, f[2] = 3;

    for(int i = 3; i < 1001; i++)

        for(int j = 1; j <= i; j++){

            int k = (c[i][j]*f[i-j]) mod;

            f[i] = (k+f[i]) mod;

        }

}

int main(){

    memset(c, 0, sizeof(c));

    memset(f, 0, sizeof(f));

    init();

    solve();

    int n, T, cases = 0;   cin >> T;

    while(T--){

        scanf("%d", &n);

        printf("Case %d: %d\n", ++cases, f[n]);

    }

    return 0;

}