#include<stdio.h>
#include<stdlib.h>

int main(){
	int q,*t,i;
	t=(int*)malloc(sizeof(int)*1000001);
	if (t==NULL) {
		fprintf(stderr,"malloc");
		return 1;
	}
	scanf("%d",&q);
	int n[q];
	t[0]=t[1]=t[2]=0;t[3]=1;
	for (i=4;i<1000000;i++) {
		t[i]=t[i-1]+t[i-2]+t[i-3]+t[i-4];
		t[i]%=17;
	}
	for (i=0;i<q;i++) { 
		scanf("%d",&n[i]);
	}
	//puts("----------------------");
	for (i=0;i<q;i++) {
		printf("%d\n",t[n[i]-1]);
	}
	free(t);
	return 0;
}