zero = len([])
one = len([()])
two = len([(),()])
seven = len([(),(),(),(),(),(),()])
nine = len([(),(),(),(),(),(),(),(),()])
ten = len([(),(),(),(),(),(),(),(),(),()])
pow_ten_9 = pow(ten, nine)
mod = sum([pow_ten_9, seven])

def multiply(A, B, mod):
    a = (A[0][0].__mul__(B[0][0])).__add__(A[0][1].__mul__(B[1][0]))
    a = divmod(a, mod)[1]
    b = (A[0][0].__mul__(B[0][1])).__add__(A[0][1].__mul__(B[1][1]))
    b = divmod(b, mod)[1]
    c = (A[1][0].__mul__(B[0][0])).__add__(A[1][1].__mul__(B[1][0]))
    c = divmod(c, mod)[1]
    d = (A[1][0].__mul__(B[0][1])).__add__(A[1][1].__mul__(B[1][1]))
    d = divmod(d, mod)[1]
    return [[a, b], [c, d]]

def matrix_pow(mat, power, mod):
    result = [[one, zero], [zero, one]]
    while power > zero:
        if (power & one) == one:
            result = multiply(result, mat, mod)
        mat = multiply(mat, mat, mod)
        power = power >> one
    return result

T = int(input())
for _ in range(T):
    n = int(input())
    if n == zero:
        ans = divmod(two, mod)[1]
    elif n == one:
        ans = divmod(one, mod)[1]
    else:
        mat = [[one, one], [one, zero]]
        power = n.__sub__(one)
        mat_pow = matrix_pow(mat, power, mod)
        a = mat_pow[0][0]
        b = mat_pow[0][1]
        term = (a.__mul__(one)).__add__(b.__mul__(two))
        ans = divmod(term, mod)[1]
    print(ans)