array = [[0 for j in range(8)] for i in range(10005)];

array[1][1]=1;
array[1][3]=1;
array[1][5]=1;
array[1][7]=1;

for i in range(1,10000):
    array[i+1][3] += array[i][1];
    array[i+1][1] += array[i][3];
    array[i+1][5] += array[i][3];
    array[i+1][7] += array[i][5];
    array[i+1][5] += array[i][7];
    array[i+1][3] += array[i][7];

t=int(input(''));
for j in range(t):
    n=int(input(''))
    print(array[n][1]+array[n][3]+array[n][5]+array[n][7]);