import operator as o

# Define numbers without using forbidden characters
z = len([])
a = len([z])
b = len([z, a])
c = len([z, a, b])
d = len([z, a, b, c])
e = len([z, a, b, c, d])
f = len([z, a, b, c, d, e])
g = len([z, a, b, c, d, e, f])
h = len([z, a, b, c, d, e, f, g])
i = len([z, a, b, c, d, e, f, g, h])
j = len([z, a, b, c, d, e, f, g, h, i])
k = o.add(o.pow(j, i), g)

# Matrix multiplication and exponentiation functions
def mmul(m1, m2):
    return (
        (o.add(o.mul(m1[0][0], m2[0][0]), o.mul(m1[0][1], m2[1][0])) % k,
         o.add(o.mul(m1[0][0], m2[0][1]), o.mul(m1[0][1], m2[1][1])) % k),
        (o.add(o.mul(m1[1][0], m2[0][0]), o.mul(m1[1][1], m2[1][0])) % k,
         o.add(o.mul(m1[1][0], m2[0][1]), o.mul(m1[1][1], m2[1][1])) % k)
    )

def mpow(mat, power):
    result = ((a, z), (z, a))
    while power > z:
        if power % b == a:
            result = mmul(result, mat)
        mat = mmul(mat, mat)
        power = power // b
    return result

def lucas(n):
    if n == z:
        return b % k
    mat = mpow(((a, a), (a, z)), n - a)
    return o.add(o.mul(mat[0][0], a), o.mul(mat[0][1], b)) % k

t = int(input())
for _ in range(t):
    n = int(input())
    print(lucas(n))