import operator

mod = (len('aaaaaaaaaa') ** len('aaaaaaaaa')) + len('aaaaaaa')

def mat_mult(a, b, mod):
    a00, a01 = a[0]
    a10, a11 = a[1]
    b00, b01 = b[0]
    b10, b11 = b[1]
    
    c00 = operator.add(operator.mul(a00, b00), operator.mul(a01, b10))
    c00 = divmod(c00, mod)[1]
    c01 = operator.add(operator.mul(a00, b01), operator.mul(a01, b11))
    c01 = divmod(c01, mod)[1]
    c10 = operator.add(operator.mul(a10, b00), operator.mul(a11, b10))
    c10 = divmod(c10, mod)[1]
    c11 = operator.add(operator.mul(a10, b01), operator.mul(a11, b11))
    c11 = divmod(c11, mod)[1]
    return [[c00, c01], [c10, c11]]

def matrix_pow(mat, power, mod):
    result = [[True, False], [False, True]]
    current = mat.copy()
    while power > 0:
        if divmod(power, len('aa'))[1] == len('a'):
            result = mat_mult(result, current, mod)
        current = mat_mult(current, current, mod)
        power = power >> len('a')
    return result

T = int(input())
for _ in range(T):
    n = int(input())
    if n == len('a'):
        print(len('a'))
    else:
        M = [[True, True], [True, False]]
        power = n - len('a')
        mat = matrix_pow(M, power, mod)
        a, b = mat[0]
        l_a = operator.mul(a, len('a'))
        l_b = operator.mul(b, len('aa'))
        res = operator.add(l_a, l_b)
        res = divmod(res, mod)[1]
        print(res)