# 9507 Generations of Tribbles

t = int(input()) # 0<t<69 

data = []
for i in range(t):
  data.append(int(input()))

cnt = [1,1,2,4,8]

for i in range(5,68):
  cnt.append(cnt[i-1]+cnt[i-2]+cnt[i-3]+cnt[i-4])

for i in data:
  print(cnt[i])