#include<bits/stdc++.h>
using namespace std;
const int mod=19260817;
struct jk{
	int a[5][5];
}cs;
jk qwq(jk x,jk y){
	jk ui;
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			ui.a[i][j]=0;
		}
	}
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			for(int k=1;k<=3;k++){
				ui.a[i][j]=(ui.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
			}
		}
	}
	return ui;
}
jk ksm(jk a,int b){
	jk res;
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			if(i==j){
				res.a[i][j]=1;
			}
			else{
				res.a[i][j]=0;
			}
		}
	}
	while(b){
		if(b&1){
			res=qwq(res,a);
		}
		a=qwq(a,a);
		b>>=1;
	}
	return res;
}
int tyu[5];
int zxc[5]; 
void uiop(jk cvb){
	for(int i=1;i<=3;i++){
		zxc[i]=0;
	}
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			zxc[i]=((cvb.a[j][i]*tyu[j])%mod+(zxc[i]%mod))%mod;
		}
	}
	return ;
}
int main(){
	int m,n;
	cin>>m;
	cs.a[1][1]=1;
	cs.a[2][1]=1;
	cs.a[3][1]=1;
	cs.a[1][2]=1;
	cs.a[2][2]=0;
	cs.a[3][2]=0;
	cs.a[1][3]=0;
	cs.a[2][3]=1;
	cs.a[3][3]=0;
	while(m--){
		cin>>n;
		jk qwer=ksm(cs,n);
		tyu[1]=1;
		tyu[2]=0;
		tyu[3]=0;
		uiop(qwer);
		cout<<(zxc[1]+zxc[2]+zxc[3])%mod<<endl;
	} 
	return 0;
}

wa #4,5,6,7,8,10