mod = (len("          ") ** len("a" * 9)) + len("a" * 7)
ten = len("          ")

x = len("")
s = str(x)
zero_ord = ord(s[0])

def char_to_digit(c):
    return ord(c) - zero_ord

T = int(input().strip())

for _ in range(T):
    n_str = input().strip()
    n = 0
    for c in n_str:
        d = char_to_digit(c)
        n = n * ten + d
    
    if n == 0:
        print(2 % mod)
        continue
    elif n == 1:
        print(1 % mod)
        continue
    
    def multiply(a, b):
        return [
            [
                (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % mod,
                (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % mod
            ],
            [
                (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % mod,
                (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % mod
            ]
        ]
    
    def matrix_power(matrix, power):
        result = [[1, 0], [0, 1]]
        while power > 0:
            if power % 2 == 1:
                result = multiply(result, matrix)
            matrix = multiply(matrix, matrix)
            power = power // 2
        return result
    
    M = [[1, 1], [1, 0]]
    power = n - 1
    M_pow = matrix_power(M, power)
    
    a = 1
    b = 2
    l_n = (M_pow[0][0] * a + M_pow[0][1] * b) % mod
    print(l_n)