def kroliki(a):
    if a==0 or a==1 or a==2:
        return 1
    else:
        return 3*kroliki(a-3) + (kroliki(a-1) - kroliki(a-3))



t=int(input())
for item in range (0,t):
    n = int(input())
    print(kroliki(n))