def f(num):
if num==10:
return 1
elif num==20:
return 3
else:
result= f(num-10) + 2* f(num-20)
num-=10
return result
for tc in range(1, int(input())+1):
n = int(input())
total = f(n)
print(f'#{tc} {total}')10,20일 경우를 제외하고(전/전전단계가 존재하지 않음)
모두 바로 전단계(-10)의 값과 전전단계(-20)*2의 값의 합을 답으로 가진다.
