//看了冰學長的思路才明白
// 當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;
}