def tetra_nacci(k, t):

	def calc(i):
		while True:
			if i in t.keys():
				return t[i]
			elif i-1 in t.keys():
				t[i] = t[i-1]+t[i-2]+t[i-3]+t[i-4]
				return t[i]
			elif i-2 in t.keys():
				t[i-1] = t[i-2]+t[i-3]+t[i-4]+t[i-5]
				t[i] = t[i-1]+t[i-2]+t[i-3]+t[i-4]
				return t[i]
			elif i-3 in t.keys():
				t[i-2] = t[i-3]+t[i-4]+t[i-5]+t[i-6]
				t[i-1] = t[i-2]+t[i-3]+t[i-4]+t[i-5]
				t[i] = t[i-1]+t[i-2]+t[i-3]+t[i-4]
				return t[i]
			elif i-4 in t.keys():
				t[i-3] = t[i-4]+t[i-5]+t[i-6]+t[i-7]
				t[i-2] = t[i-3]+t[i-4]+t[i-5]+t[i-6]
				t[i-1] = t[i-2]+t[i-3]+t[i-4]+t[i-5]
				t[i] = t[i-1]+t[i-2]+t[i-3]+t[i-4]
				return t[i]
			calc(i-4)

	if k in t:
		return t
	else:
		t[k] = calc(k)
		return t

q = int(input())
n_lst = [0]*q
for i in range(q):
	n_lst[i] = int(input())

t_dct = {-3:0, -2:0, -1:0, 0:0, 1:0, 2:0, 3:0, 4:1}
for i in range(q):
	k_lst = sorted(t_dct.keys())
	while k_lst[-1] + 1000 < n_lst[i]:
		t_dct = tetra_nacci(k_lst[-1]+1000, t_dct)
		k_lst = sorted(t_dct.keys())
	t_dct = tetra_nacci(n_lst[i], t_dct)
	print(t_dct[n_lst[i]])