#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

using namespace std;

struct Mat{

 int mat[][];

};

Mat it,E,E0;

void init()

{

    memset(it.mat,,sizeof (Mat));

    memset(E.mat,,sizeof (Mat));

    memset(E0.mat,,sizeof (Mat));

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

        E.mat[i][i]=;

    it.mat[][]=;

    it.mat[][]=;

    it.mat[][]=;

    it.mat[][]=;

    it.mat[][]=;

    it.mat[][]=;

    it.mat[][]=;

    it.mat[][]=;

    it.mat[][]=;

}

Mat operator*(Mat a,Mat b)

{

    Mat c;

    c=E0;

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

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

        for (int k=;k<;k++)

    {

        if (a.mat[i][k] && b.mat[k][j])

        {

            c.mat[i][j]+=a.mat[i][k]*b.mat[k][j];

            c.mat[i][j]%=;

        }

    }

    return c;

}

Mat operator^(Mat a,int x)

{

    Mat c=E;

    for (;x;x>>=)

    {

        if (x&)

            c=c*a;

        a=a*a;

    }

    return c;

}

int main()

{

    init();

    int t;

    scanf("%d",&t);

    int counts=;

    while (t--)

    {

        int n;

        scanf("%d",&n);

        int ans=;

        printf("Case %d: ",++counts);

        if (n>=){

        Mat s=it^(n-);

        ans=s.mat[][]*+s.mat[][]*+s.mat[][]*+s.mat[][];

        ans%=;

        }

        if (n==) ans=;

        if (n==) ans=;

        if (n==) ans=;

        printf("%d\n",ans);

    }

    return ;

}