def mult(a,b):
	n = len(a)
	m = len(a[0])
	l = len(b[0])
	
	ans = [[0 for _ in range(l)] for __ in range(n)]
	for i in range(n):
		for j in range(l):
			calc = 0
			for k in range(m):
				calc += a[i][k]*b[k][j]
			ans[i][j] = calc
	
	return ans

# Exp. rapida de matrices
# Realiza O(log(n)) multiplicaciones de matrices
def binexp(A,n):
	if n == 1:
		return A
	if n % 2 == 0:
		preans = binexp(A,n//2)
		return mult(preans,preans)
	preans = binexp(A,(n-1)//2)
	preans = mult(preans,preans)
	return mult(preans,A)

# Transformación
A = [
	[1,0,4,0],
	[1,0,0,0],
	[0,0,1,1],
	[0,0,1,0]
]

# Matriz original
# [[g(1)],[g(0)],[f(2)],[f(1)]]
B = [
	[4],
	[0],
	[1],
	[1]
]

def perimeter(n):
	ans = mult(binexp(A,n),B)
	return ans[1][0]

n_testcase = int(input())
for _ in range(n_testcase):
	n = int(input())
	print(perimeter(n))