test $1\sim 5$ AC，test $6\sim 10$ RE

def mul(A, B):
  C = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
  for i in range(3):
    for j in range(3):
      for k in range(3):
        C[i][j] += A[i][k] * B[k][j]
        return C
      def pow(A, k):
        ans = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
        while (k > 0):
          if k & 1:
            ans = mul(ans, A)
            A = mul(A, A)
            k >>= 1
            return ans
          A = [[1, 0, 1], [0, 0, 0], [0, 0, 0]]
          B = [[1, 0, 1], [0, 0, 2], [0, 1, 1]]
          m = int(input())
          for _ in range(m):
            n = int(input())
            print(mul(A, pow(B, n-1))[0][2])