#include<iostream>
using namespace std;
int t[1<<17];
main()
{
	t[4]=1;
	for(int i=5;i<5000;i++)
	{
		t[i]=(t[i-1]+t[i-2]+t[i-3]+t[i-4])%17;
	}
	int q;cin>>q;
	for(;q--;)
	{
		int n;cin>>n;
		cout<<t[(n-1)%4912+1]<<endl;
	}
}