import sys
input = sys.stdin.readline
t=int(input())
arr=[]
for i in range(t):
arr.append(int(input())) #입력 받기
p=[0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9]#p(1)~p(10) p(0)은 사용하지 않으므로 0으로 선언
for i in range(len(p),max(arr)+1):#11부터 입력 받은 숫자 중 가장 큰 숫자까지
p.append(p[i-2]+p[i-3])
for i in arr:
print(p[i])
접근 방법