t[1010100];
long long i;

main(){
	t[4]=1;
	for(i=5;i<1000001;++i){
		t[i]=(t[i-1]+t[i-2]+t[i-3]+t[i-4])%17;
	}
	for(scanf("%d",&i);~scanf("%lld",&i);){
		printf("%d\n",t[i%4912]);
	}
}