//看了冰学长的思路才明白
// 当n>=3时可以全部由2x2的方砖镶嵌得到
//eg:
// 用 [**] 表示
// [**] 一块2x2的方砖
// n=15 时
//[**][**][**][**][**][**][**] *
//[**][**][**][**][**][**][**] *
//* [**][**][**][**][**][**][**]
//* [**][**][**][**][**][**][**]
//
//dp[i]可以由dp[i-1]+一列1x1方砖(1种) 或者dp[n-2]+由含2x2的方砖组成的两列(4种) 或者dp[n-3]+由含3x3的方砖组成的3列(2种) 或或者dp[n-4]+由含4x4的方砖组成的四列(1种)
//
//还可以由dp[n-3～0]+(3～n)列由2x2方砖镶嵌 得到
//
#include<stdio.h>
#include<string.h>
#define mod 19890907
int dp[110];
int main()
{
int n,t;
int i;
int l;
dp[0]=1;
dp[1]=1;
dp[2]=dp[1]+4*dp[0];
dp[3]=dp[2]+4*dp[1]+2*dp[0]+2*dp[0];
dp[4]=dp[3]+4*dp[2]+2*dp[1]+dp[0]+2*dp[1]+2*dp[0];
for(i=5;i<=100;i++)
{
dp[i]=dp[i-1]+4*dp[i-2]+2*dp[i-3]+dp[i-4];
dp[i]=dp[i]%mod;
for(l=3;l<=i;l++)dp[i]=(dp[i]+2*dp[i-l])%mod;//计算末尾由2x2方砖镶嵌组成且长度为l由多少种情况
}
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%d\n",dp[n]);
}
return 0;
}