t[1010100];
long long i;

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