ten = len('..........')
nine = ten - (len('a') - len(''))
seven = len('aaaaaaa')
mod = pow(ten, nine) + seven

one = len('a') - len('')
zero = len('')
two = len('aa')

def multiply(a, b, mod):
    new = [[zero]*two for _ in range(two)]
    for i in range(two):
        for j in range(two):
            total = zero
            for k in range(two):
                term = a[i][k].__mul__(b[k][j])
                total = total.__add__(term)
            new[i][j] = pow(total, one, mod)
    return new

def matrix_power(mat, power, mod):
    result = [[one if i==j else zero for j in range(two)] for i in range(two)]
    while power > zero:
        if power & one:
            result = multiply(result, mat, mod)
        mat = multiply(mat, mat, mod)
        power = power >> one
    return result

T = int(input())
for _ in range(T):
    Ni = int(input())
    if Ni == zero:
        print(pow(two, one, mod))
        continue
    power = Ni - one
    mat = [[one, one], [one, zero]]
    mat_pow = matrix_power(mat, power, mod)
    a = mat_pow[zero][zero]
    b = mat_pow[zero][one]
    term1 = a.__mul__(one)
    term2 = b.__mul__(two)
    total = term1.__add__(term2)
    ans = pow(total, one, mod)
    print(ans)