import operator as op

zero = len("")
one = len("x")
mod = op.add(op.pow(len(".........."), len(".........")), len("......."))

def multiply(a, b):
    a00 = a[zero][zero]
    a01 = a[zero][one]
    a10 = a[one][zero]
    a11 = a[one][one]
    b00 = b[zero][zero]
    b01 = b[zero][one]
    b10 = b[one][zero]
    b11 = b[one][one]
    c00 = op.mod(op.add(op.mul(a00, b00), op.mul(a01, b10)), mod)
    c01 = op.mod(op.add(op.mul(a00, b01), op.mul(a01, b11)), mod)
    c10 = op.mod(op.add(op.mul(a10, b00), op.mul(a11, b10)), mod)
    c11 = op.mod(op.add(op.mul(a10, b01), op.mul(a11, b11)), mod)
    return [[c00, c01], [c10, c11]]

def matrix_pow(mat, power):
    result = [[one, zero], [zero, one]]
    while op.gt(power, zero):
        if op.eq(op.mod(power, op.add(one, one)), one):
            result = multiply(result, mat)
        mat = multiply(mat, mat)
        power = op.floordiv(power, op.add(one, one))
    return result

def compute_lucas(n):
    if op.eq(n, zero):
        return op.mod(op.add(one, one), mod)
    elif op.eq(n, one):
        return op.mod(one, mod)
    else:
        exponent = op.add(n, ~zero)
        mat_pow = matrix_pow([[one, one], [one, zero]], exponent)
        L1 = one
        L0 = op.add(one, one)
        term1 = op.mul(mat_pow[zero][zero], L1)
        term2 = op.mul(mat_pow[zero][one], L0)
        l_n = op.add(term1, term2)
        return op.mod(l_n, mod)

T = int(input())
for _ in range(T):
    Ni = int(input())
    print(compute_lucas(Ni))