#include<bits/stdc++.h>
using namespace std;

int Z[4][4];

void f(int a[4][4]){
	int r[4][4];
	for(int y=0;y<4;++y){
		for(int x=0;x<4;++x){
			r[y][x]=0;
		}
	}
	for(int y=0;y<4;++y){
		for(int x=0;x<4;++x){
			for(int i=0;i<4;++i){
				(r[y][x]+=Z[y][i]*a[i][x])%=17;
			}
		}
	}
	for(int y=0;y<4;++y){
		for(int x=0;x<4;++x){
			Z[y][x]=r[y][x];
		}
	}
}

main(){
	int Q;
	scanf("%d",&Q);
	for(int i=0;i<Q;++i){
		long long n;
		scanf("%lld",&n);
		--n;
		for(int y=0;y<4;++y){
			for(int x=0;x<4;++x){
				Z[y][x]=x==y;
			}
		}
		for(int i=60;i--;){
			f(Z);
			if(n>>i&1){
				int a[4][4];
				for(int y=0;y<4;++y){
					for(int x=0;x<4;++x){
						a[y][x]=y==0|y-1==x;
					}
				}
				f(a);
			}
		}
		printf("%d\n",Z[3][0]);
	}
}