rt。后五个点 RE。

代码：

class Matrix:
    def __init__(self):
        self.a = [[0] * 4 for _ in range(4)]

    def __mul__(self, other):
        result = Matrix()
        for i in range(1, 4):
            for j in range(1, 4):
                for k in range(1, 4):
                    result.a[i][j] += self.a[i][k] * other.a[k][j]
        return result


def qpow(exponent):
    global ans, base
    while exponent:
        if exponent & 1:
            ans = ans * base
        base = base * base
        exponent >>= 1


ans = Matrix()
base = Matrix()

uu = int(input())
for _ in range(uu):
    n = int(input())
    if n == 1:
        print("1")
        continue
    if n == 2:
        print("2")
        continue
    base.a = [[0] * 4 for _ in range(4)]
    base.a[1][1] = base.a[1][3] = base.a[3][2] = base.a[3][3] = 1
    base.a[2][3] = 2
    ans.a[1][1] = ans.a[1][2] = 1
    ans.a[1][3] = 2
    qpow(n - 2)
    print(ans.a[1][3])