one = True
zero = one - one
two = one + one
three = two + one
four = three + one
five = four + one
six = five + one
seven = six + one
eight = seven + one
nine = eight + one
ten = nine + one
mod = (ten ** nine) + seven

def add(x, y):
    x += y
    if x >= mod:
        x -= mod
    return x

def subtract(x, y):
    x -= y
    if x < zero:
        x += mod
    return x

def multiply(a, b):
    a = add(a, zero)
    b = add(b, zero)
    res = zero
    while b > zero:
        if b & one:
            res = add(res, a)
        a = add(a, a)
        b = b >> one
    return res

def lucas(n):
    if n == zero:
        return two
    a, b, s = two, one, one
    mask = one << (n.bit_length() - one)
    while mask > zero:
        a_sq = multiply(a, a)
        two_s = multiply(two, s)
        c = subtract(a_sq, two_s)
        ab = multiply(a, b)
        d = subtract(ab, s)
        new_a, new_b = c, d
        new_s = one
        if n & mask:
            new_a = d
            new_b = add(c, d)
            new_s = subtract(zero, one)
        a, b, s = new_a, new_b, new_s
        mask = mask >> one
    return a

import sys

T = int(sys.stdin.readline())
for _ in range(T):
    n = int(sys.stdin.readline())
    print(lucas(n))