zero = len([])
one = len([[]])
two = len('aa')
five = len('aaaaa')
nine = len('aaaaaaaaa')
seven = len('aaaaaaa')
mod = (five * two) ** nine + seven

def multiply(m1, m2, mod):
    z = len([])
    o = len([[]])
    sum_val = m1[z][z] * m2[z][z] + m1[z][o] * m2[o][z]
    _, a = divmod(sum_val, mod)
    sum_val = m1[z][z] * m2[z][o] + m1[z][o] * m2[o][o]
    _, b = divmod(sum_val, mod)
    sum_val = m1[o][z] * m2[z][z] + m1[o][o] * m2[o][z]
    _, c = divmod(sum_val, mod)
    sum_val = m1[o][z] * m2[z][o] + m1[o][o] * m2[o][o]
    _, d = divmod(sum_val, mod)
    return [[a, b], [c, d]]

def matrix_pow(mat, power, mod):
    z = len([])
    o = len([[]])
    result = [[o, z], [z, o]]
    current = mat
    while power > z:
        _, rem = divmod(power, two)
        if rem == o:
            result = multiply(result, current, mod)
        current = multiply(current, current, mod)
        power = power >> o
    return result

t = int(input())
for _ in range(t):
    N = int(input())
    if N == one:
        _, ans = divmod(one, mod)
        print(ans)
    else:
        mat = [[one, one], [one, zero]]
        power = N - one
        mat_exp = matrix_pow(mat, power, mod)
        z = len([])
        o = len([[]])
        a_row = mat_exp[z]
        vec = [one, two]
        sum_val = a_row[z] * vec[z] + a_row[o] * vec[o]
        _, ans = divmod(sum_val, mod)
        print(ans)