//Accepted 220 KB 359 ms
#include <cstdio>
#include <cstring>
;
int pp;
struct matrix
{
//矩阵m*n
//(0,0)..(m-1,n-1)
int a[maxn][maxn];
int m,n;
matrix()
{
memset(a,,sizeof(a));
m=n=;
}
matrix operator+(matrix mymatrix)
{
matrix m_matrix;
int i,j;
;i<m;i++)
;j<n;j++)
m_matrix.a[i][j]=(a[i][j]+mymatrix.a[i][j])%pp;
m_matrix.m=m;
m_matrix.n=n;
return m_matrix;
}
matrix operator*(matrix mymatrix)
{
matrix m_matrix;
int i,j,k;
;i<m;i++)
{
;j<n;j++)
{
if (a[i][j])
;k<mymatrix.n;k++)
m_matrix.a[i][k]=(m_matrix.a[i][k]+a[i][j]*mymatrix.a[j][k])%pp;
}
}
m_matrix.m=m;
m_matrix.n=mymatrix.n;
return m_matrix;
}
//A^k
matrix getp(int k)
{
matrix d,c;
) return *this;
) return (*this)*(*this);
d=getp(k/);
==) return d*d;
else
return d*d*(*this);
}
//A+A^2+A^3+..+A^k
matrix sump(int k)
{
matrix d,c;
) return *this;
) return (*this)+(*this)*(*this);
d=sump(k/);
==)
{
);
}
else
)+getp(k);
}
void output()
{
int i,j;
;i<m;i++)
{
;j<n;j++)
printf("%d ",a[i][j]%pp);
printf("\n");
}
}
void input()
{
;i<m;i++)
{
;j<n;j++)
{
scanf("%d",&a[i][j]);
}
}
}
};
int n;
int k;
matrix tr,mtr;
int main()
{
pp=;
int T;
scanf("%d",&T);
;t<=T;t++)
{
scanf("%d",&n);
printf("Case %d: ",t);
)
{
) printf("1\n");
) printf("4\n");
) printf("9\n");
continue ;
}
tr.m=tr.n=;
tr.a[][]=;
tr.a[][]=tr.a[][]=tr.a[][]=;
tr.a[][]=;
tr.a[][]=;
tr.a[][]=;
tr.a[][]=;
tr.a[][]=;
tr.a[][]=;
tr.a[][]=;
tr.a[][]=;
tr.a[][]=;
tr.a[][]=;
tr.a[][]=;
tr.a[][]=;
tr=tr.getp(n-);
mtr.m=;
mtr.n=;
mtr.a[][]=;
mtr.a[][]=;
mtr.a[][]=;
mtr.a[][]=;
tr=mtr*tr;
printf(][]);
}
;
}
