firstdata = int(input());
tfir = 0;
tsec = 0;
tthir = 0;
tfour = 1;
result = 0;
siteik = 0;

for inp in range(0,firstdata):
	siteik = int(input());
	if siteik < 4:
		print(0);
	elif siteik == 4:
		print(1);
	else:
		for inp2 in range(5,siteik+1):
			result = (tfir + tsec + tthir + tfour)%17;
			tfir = tsec;
			tsec = tthir;
			tthir = tfour;
			tfour = result;
		print(result);
		tfir = 0;
		tsec = 0;
		tthir = 0;
		tfour = 1;