UVa 11310 - Delivery Debacle Solution

a=[None]*41
def rec(n):
    if n==1:
        return 1
    elif n==2:
        return 5
    elif n==3:
        return 11
    elif a[n] is not None:
        return a[n]
    a[n]=rec(n-1)+4*rec(n-2)+2*rec(n-3)
    return a[n]
def Main():
    t=int(input())
    while t>0:
        t-=1;
        x=int(input())
        print(rec(x))
if __name__=='__main__':
    Main()