topc2024 pF

import math

mod = 10 ** 10

def p(a, b):
  l = [
    [(a[0][0] * b[0][0] + a[0][1] * a[1][0]) % mod, (a[0][0] * b[0][1] + a[0][1] * a[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]
  ]
  return l

def fib(n):
  init = [[1, 1], [1, 0]]
  ans = [[1, 1], [1, 0]]
  count = 0
  while n > 0:
    count += 1
    if n % 2 == 1:
      ans = p(ans, init)
    n = n // 2
    temp = init
    init = p(init, temp)
  return ans[1][1]

def fpow(base, n, m):
    res = 1
    while n > 0:
        if (n%2) == 1: 
            res = (res * base) % m
        base = (base * base) % m
        n = n // 2
    return res

# pisano number of 10^10
lim = 15000000000
q = int(input())
while q > 0:
    q -= 1
    n = int(input())
    
    n1 = fpow(7,n,lim)
    n2 = fpow(7,n1,lim)
    n3 = fpow(7,n2,lim)
    
    print(fib(n3))