Read problem statements in [Mandarin Chinese] and [Bengali].

Let's define Fibonacci concatenation sequence as follows:

f[0] = 0, f[1] = 1

f[i] = f[i-1] + f[i-2], for every i ≥ 2

Here f[i] denotes the i^{th} Fibonacci concatenation number and + represents concatenation.

For example, f[2] = f[1] + f[0] = 1 + 0 = 10, f[3] = f[2] + f[1] = 10 + 1 =  101.

Given an integer n, you have to determine the sum of digits of all subsequences of the n^{th} Fibonacci concatenation number f[n],  modulo 10^{9} + 7.

A *subsequence* of a number is a sequence of digits that can be derived from the number by deletion of several (possibly, zero or all) digits without changing the order of the remaining digits. The subsequence may even start with trailing zeros. For example 10, 01 are subsequences of 101 while 110 is NOT a subsequence of 101. Note that there are 8 subsequences of 101. The subsequence 1 appears twice and should be counted as different while computing the sum.

------ Input Format ------ 

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first and only line of each test case contains a single integer n.

------ Output Format ------ 

For each test case, print a single line containing one integer - the sum of digits of all subsequences of f[n], modulo 10^{9} + 7.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ n ≤ 10^{5}$

----- Sample Input 1 ------ 
3
1
2
3

----- Sample Output 1 ------ 
1
2
8

----- explanation 1 ------ 
Test case $1$: Since $f[1]=1$, we have only two subsequences, "" (empty subsequence) and "$1$". So the sum of digits of both subsequences is $ 0 + 1 = 1$.

Test case $2$: Since $f[2] = 10$, we have four subsequences, "" (empty subsequence), "$1$", "$0$" and "$10$". So the sum of digits of all the subsequences is $0 + 1 + 0 + 1 = 2$.

Difficulty: VERY_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
l = [0] * (10 ** 5 + 1)
k = [0] * (10 ** 5 + 1)
l[0] = l[1] = 1
k[0] = 0
k[1] = 1
m = 10 ** 9 + 7
m2 = m - 1
for i in range(2, 10 ** 5 + 1):
	k[i] = k[i - 1] + k[i - 2]
	l[i] = l[i - 1] + l[i - 2]
	k[i] %= m
	l[i] %= m2
for i in range(int(input())):
	n = int(input())
	len = l[n]
	x = k[n]
	m = 10 ** 9 + 7
	y = x * pow(2, (len - 1) % m2, m)
	print(y % m)


n = 10 ** 5 + 2
dp = [0] * n
m = 10 ** 9 + 7
arr = [0] * n
arr2 = [0] * n
arr[1] = 1
arr2[0] = 1
arr2[1] = 1
m2 = 1000000006
for i in range(2, n):
	arr[i] = (arr[i - 1] + arr[i - 2]) % m
	arr2[i] = (arr2[i - 1] + arr2[i - 2]) % m2
for i in range(0, n):
	dp[i] = arr[i] * pow(2, arr2[i] - 1, m) % m
for _ in range(int(input())):
	k = int(input())
	print(dp[k])


MAX = 100000
MOD = 10 ** 9 + 7
fib_pow = [2, 2] + [0] * MAX
dp = [0, 1] + [0] * MAX
for i in range(2, MAX + 1):
	fib_pow[i] = fib_pow[i - 1] * fib_pow[i - 2] % MOD
	dp[i] = (dp[i - 1] * fib_pow[i - 2] % MOD + dp[i - 2] * fib_pow[i - 1] % MOD) % MOD
for _ in range(int(input())):
	print(dp[int(input())])


dp = [0] * (100000 + 2)
fibPow = [0] * (100000 + 2)
fibPow[0] = 2
fibPow[1] = 2
dp[1] = 1
m = 1000000007
for i in range(2, 100000 + 2):
	fibPow[i] = fibPow[i - 1] * fibPow[i - 2] % m
	dp[i] = (dp[i - 1] * fibPow[i - 2] % m + dp[i - 2] * fibPow[i - 1] % m) % m
for _ in range(int(input())):
	n = int(input())
	print(dp[n])


try:
	n = int(input())
	fib = [0, 1, 2]
	po = [1, 2, 4]
	k = 10 ** 9 + 7
	li = []
	for i in range(n):
		x = int(input())
		li.append(x)
		if x < len(fib):
			y = fib[x]
		else:
			for i in range(len(fib), x + 1):
				c = (fib[i - 1] * po[i - 2] + fib[i - 2] * po[i - 1]) % k
				po.append(po[i - 2] * po[i - 1] % k)
				fib.append(c)
			y = fib[x]
		print(y)
except:
	pass


import itertools
import math
from sys import stdin

def A():
	a = [int(x) for x in stdin.readline().split()]
	n = a[0]
	print(int(n * (n / 2)))

def B():
	t = int(input())
	while t:
		t -= 1
		b = [int(x) for x in stdin.readline().split()]
		(n, a) = (b[0], b[1])
		res = 0
		for i in range(n, -1, -1):
			if math.sqrt(i) * math.sqrt(i) == i:
				res = max(res, int(math.sqrt(i)) * a)
				break
		print(res)

def C():
	t = int(input())
	while t:
		t -= 1
		b = [int(x) for x in stdin.readline().split()]
		(n, m, q) = (b[0], b[1], b[2])
		res = True
		cnt = 0
		dp = [0] * (n + 1)
		cnt = 0
		while q:
			q -= 1
			b = input().split()
			i = int(b[1])
			if b[0] == '+':
				if dp[i] == 1:
					res = False
				dp[i] = 1
				cnt += 1
			else:
				if dp[i] == 0:
					res = False
				dp[i] = 0
				cnt -= 1
			if cnt > m:
				res = False
		if res:
			print('Consistent')
		else:
			print('Inconsistent')

def D():
	t = int(input())
	while t:
		t -= 1
		(n, k) = [int(x) for x in stdin.readline().split()]
		s = input()
		pos = []
		for i in range(0, len(s)):
			if s[i] == '1':
				pos.append(i)
		cnt = 1
		if len(pos) == 0:
			cnt = 0
		if len(pos) > 0:
			pos[0] += 1
		for i in range(1, len(pos)):
			if pos[i] - pos[i - 1] == k:
				continue
			if pos[i] - pos[i - 1] < k:
				pos[i] += 1
			elif pos[i] - pos[i - 1] <= k + 1:
				pos[i] -= 1
			else:
				pos[i] += 1
				cnt += 1
		print(cnt)

def E():
	mod = 1000000007
	f = [0] * (10 ** 5 + 10)
	f1 = [0] * (10 ** 5 + 10)
	f[0] = 0
	f[1] = 1
	f1[0] = 1
	f1[1] = 1

	def power(base, pow):
		res = 1
		while pow:
			if pow & 1:
				res *= base
			pow >>= 1
			base *= base
			base %= mod
			res % mod
		return res
	for i in range(2, 10 ** 5 + 10):
		f[i] = (f[i - 1] + f[i - 2]) % mod
		f1[i] = (f1[i - 1] + f1[i - 2]) % (mod - 1)
	t = int(input())
	while t:
		t -= 1
		n = int(input())
		ans = f[n] * power(2, f1[n] - 1) % mod
		print(ans)
E()


mod = 10 ** 9 + 7
f = [[0, 1], [1, 1]]
for i in range(10 ** 5):
	a = f[-1][0] + f[-2][0]
	b = f[-1][1] + f[-2][1]
	f.append([a, b])
for _ in range(int(input())):
	n = int(input())
	ans = f[n][0] % mod * pow(2, (f[n][1] - 1) % (mod - 1), mod) % mod
	print(ans)


up = 10 ** 5 + 1
mod = 10 ** 9 + 7
dig = [0] * up
ones = [0] * up
dig[0] = 1
dig[1] = 1
ones[0] = 0
ones[1] = 1
for i in range(2, up):
	dig[i] = 2 * dig[i - 1] * dig[i - 2] % mod
	ones[i] = (ones[i - 1] + ones[i - 2]) % mod
t = int(input())
for _ in range(t):
	n = int(input())
	ans = dig[n] * ones[n] % mod
	print(ans)


MOD = int(1000000000.0 + 7)
t = int(input())
ones = [0] * (10 ** 5 + 1)
size = [0] * (10 ** 5 + 1)
ones[1] = size[0] = size[1] = 1
for i in range(2, 10 ** 5 + 1):
	ones[i] = ones[i - 1] + ones[i - 2]
	size[i] = size[i - 1] + size[i - 2]
for _ in range(t):
	n = int(input())
	number_ones = ones[n] % MOD
	exponent = (size[n] - 1) % (MOD - 1)
	ans = number_ones * pow(2, exponent, MOD)
	print(int(ans % MOD))


from sys import stdin

def mkres(lim, m):
	(f_pre, f_cur) = (0, 1)
	(e_pre, e_cur) = (1, 1)
	r = [0, 1]
	while len(r) <= lim:
		(f_pre, f_cur) = (f_cur, (f_cur + f_pre) % m)
		(e_pre, e_cur) = (e_cur, e_cur * e_pre * 2 % m)
		r.append(f_cur * e_cur % m)
	return r
lim = 100000
res = mkres(lim, 1000000007)
T = int(input())
print(*(res[int(stdin.readline())] for _ in range(T)), sep='\n')


MOD = 1000000007
subseq_cnt = [2, 2]
dp = [0, 1]
for i in range(2, 100001):
	dp.append((dp[i - 1] * subseq_cnt[i - 2] % MOD + dp[i - 2] * subseq_cnt[i - 1] % MOD) % MOD)
	subseq_cnt.append(subseq_cnt[i - 1] * subseq_cnt[i - 2] % MOD)
t = int(input())
while t > 0:
	n = int(input())
	print(dp[n])
	t = t - 1


from sys import stdin

def mkfib(lim, m):
	e = [1, 1]
	f = [0, 1]
	while len(f) <= lim:
		e.append(e[-1] * e[-2] * 2 % m)
		f.append((f[-1] + f[-2]) % m)
	return (e, f)
lim = 100000
(els, fibs) = mkfib(lim, 1000000007)
T = int(input())
res = []
for tx in range(T):
	N = int(stdin.readline())
	el_subseq = els[N]
	res.append(fibs[N] * el_subseq % 1000000007)
print(*res, sep='\n')


f = [0] * (10 ** 5 + 5)
f[0] = 0
f[1] = 1
l = [0] * (10 ** 5 + 5)
l[0] = 1
l[1] = 1
m2 = 1000000006
m = 10 ** 9 + 7
for i in range(2, 10 ** 5 + 4):
	f[i] += (f[i - 1] + f[i - 2]) % m
	l[i] = (l[i - 1] + l[i - 2]) % m2
for t in range(int(input())):
	n = int(input())
	m = 10 ** 9 + 7

	def be(b, p):
		r = 1
		b = b % m
		if b == 0:
			return 0
		while p > 0:
			if p % 2:
				r = r * b % m
				p -= 1
			p = p >> 1
			b = b * b % m
		return r
	k = be(2, (l[n] - 1) % m2) % m
	d = f[n]
	print(d * k % m)


import sys
import math
import heapq
from collections import defaultdict as dd
from collections import OrderedDict as od
from collections import deque
from itertools import permutations as pp
from itertools import combinations as cc
from sys import stdin
from functools import cmp_to_key
from functools import lru_cache
from bisect import bisect_left as bs_l
from bisect import bisect_right as bs_r
input = sys.stdin.readline
mod = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 5)
dp = [0] * (10 ** 5 + 1)
dp[0] = [1, 0]
dp[1] = [1, 1]
dp1 = [-1] * (10 ** 5 + 1)
for i in range(2, 10 ** 5 + 1):
	dp[i] = [dp[i - 1][0] + dp[i - 2][0], dp[i - 1][1] + dp[i - 2][1]]
T = int(input())
for _ in range(T):
	n = int(input())
	if dp1[n] != -1:
		ans = dp1[n]
	else:
		xx = (dp[n][0] - 1) % (mod - 1)
		ans = pow(2, xx, mod) * dp[n][1] % mod
		dp1[n] = ans
	print(ans)


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
depth = 1000005
sys.setrecursionlimit(depth)
from math import inf, ceil
from collections import defaultdict

def fibonacci(n, mod):
	if n < 0:
		raise ValueError('Negative arguments not implemented')
	return _fib(n, mod)[0]

def _fib(n, mod):
	if n == 0:
		return (0, 1)
	else:
		(a, b) = _fib(n // 2, mod)
		c = a * ((b * 2 - a) % mod) % mod
		d = (a * a % mod + b * b % mod) % mod
		if n % 2 == 0:
			return (c, d)
		else:
			return (d, (c + d) % mod)

def power(a, b):
	a %= mod
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % mod
		a = a * a % mod
		b >>= 1
	return res
for _ in range(int(input())):
	n = int(input())
	mod = 1000000007
	k = fibonacci(n, mod)
	l = fibonacci(n + 1, mod - 1)
	if l == 0:
		l = mod - 2
	else:
		l = l - 1
	ans = k * power(2, l) % mod
	print(ans)


def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
t = int(input())
fibo = [[0, 0] for i in range(100001)]
fibo[0][0] = 0
fibo[0][1] = 1
fibo[1][0] = 1
fibo[1][1] = 1
for i in range(2, 100001):
	fibo[i][0] = fibo[i - 1][0] + fibo[i - 2][0]
	fibo[i][1] = fibo[i - 1][1] + fibo[i - 2][1]
for _ in range(t):
	n = int(input())
	p = 1000000007
	exp = power(2, (fibo[n][1] - 1) % (p - 1), p)
	ans = fibo[n][0] % p * (exp % p) % p
	print(ans)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = inp()
p = 10 ** 9 + 7
f = [1, 2]
fi = 1
si = 1
fi1 = 1
si1 = 1
for i in range(3, 10 ** 5 + 1):
	tt = si + fi
	tt1 = si1 + fi1
	tt1 %= p - 1
	tt %= p
	fi = si % p
	si = tt
	fi1 = si1
	si1 = tt1
	xx = tt * pow(2, (tt1 + fi1 - 1) % (p - 1), p)
	xx %= p
	f.append(xx)
while t:
	t -= 1
	n = inp()
	print(f[n - 1])


m = 1000000007
n = 100001
f = [0] * n
f[1] = 1
a = [0] * n
b = [0] * n
a[0] = 1
b[1] = 1
a[1] = 1

def power(x, y):
	temp = 0
	if y == 0:
		return 1
	temp = power(x, int(y / 2)) % m
	if y % 2 == 0:
		return temp * temp % m
	else:
		return x * temp % m * temp % m
for i in range(2, n):
	a[i] = a[i - 1] + a[i - 2]
	b[i] = b[i - 1] + b[i - 2]
	a[i] %= m - 1
	b[i] %= m
	f[i] = b[i] * power(2, (a[i] - 1) % (m - 1)) % m

def solve():
	x = int(input())
	print(f[x])
t = 1
t = int(input())
for _ in range(t):
	solve()


n = 10 ** 5
a = [0] * (n + 1)
a[1] = 1
b = [0] * (n + 1)
b[0] = 1
b[1] = 1
mod = 10 ** 9 + 7
for i in range(2, n + 1):
	a[i] = (a[i - 1] + a[i - 2]) % mod
	b[i] = b[i - 1] * b[i - 2] * 2 % mod
for _ in range(int(input())):
	n = int(input())
	x = a[n]
	y = b[n]
	print(x * y % mod)


n = 100000
dp = [0] * (n + 1)
(dp[0], dp[1]) = (1, 1)
for i in range(2, n + 1):
	dp[i] = dp[i - 1] + dp[i - 2]
seen = {1: 1}
mod = 10 ** 9 + 7
cases = int(input())
for _ in range(cases):
	n = int(input())
	if n in seen:
		print(seen[n])
		continue
	(ones, total) = (dp[n - 1], dp[n])
	ans = ones * pow(2, (total - 1) % (mod - 1), mod) % mod
	seen[n] = ans
	print(ans)


n = 10 ** 5
dp = [0 for _ in range(n + 1)]
dp[1] = 1
dp2 = [0 for _ in range(n + 1)]
dp2[0] = 1
dp2[1] = 1
mod = 10 ** 9 + 7
ans = [0, 1]
for i in range(2, n + 1):
	dp[i] = dp[i - 1] + dp[i - 2]
	dp2[i] = dp2[i - 1] * dp2[i - 2] * 2
	dp[i] %= mod
	dp2[i] %= mod
for _ in range(int(input())):
	n = int(input())
	a = dp[n]
	b = dp2[n]
	print(a * b % mod)


from sys import stdin, stdout
input = stdin.readline
mod = 10 ** 9 + 7
N = 10 ** 5 + 5
dp = [0 for i in range(N + 1)]
dp[1] = 1
dp2 = [0 for i in range(N + 1)]
dp2[1] = 1
dp2[0] = 1
for i in range(2, N + 1):
	dp[i] = dp[i - 1] + dp[i - 2]
	dp2[i] = dp2[i - 1] * dp2[i - 2] * 2
	dp[i] %= mod
	dp2[i] %= mod
t = int(input())
for _ in range(t):
	n = int(input())
	a = dp[n]
	b = dp2[n]
	print(a * b % mod)


t = int(input())
arr = [0] * 100002
arr[1] = 1
M = 10 ** 9 + 7

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
for i in range(2, 100002):
	arr[i] = arr[i - 1] + arr[i - 2]
for test in range(t):
	n = int(input())
	if n == 1:
		print('1')
		continue
	n_d = (arr[n + 1] - 1) % (M - 1)
	n_1 = arr[n]
	n_d = n_d % (M - 1)
	ans = power(2, n_d, M)
	ans = ans * n_1 % M
	print(ans)


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
t = int(input())
modulo = 1000000007
cases = []
for _ in range(t):
	cases.append(int(input()))
max_known = 1
max_n = max(cases)
ones = [0] * (max_n + 1)
digits = [2] * (max_n + 1)
ones[1] = 1
for n in cases:
	for i in range(max_known + 1, n + 1):
		ones[i] = (ones[i - 1] + ones[i - 2]) % modulo
		digits[i] = digits[i - 1] * digits[i - 2] % modulo
	max_known = max(n, max_known)
	print(ones[n] * digits[n] * modinv(2, modulo) % modulo)


T = int(input())
memo = [1, 1]
total = [0, 1]
mod = 1000000007
for t in range(T):
	N = int(input())
	for i in range(len(memo), N + 1):
		memo.append(memo[-1] * memo[-2] * 2 % mod)
		total.append((total[-1] + total[-2]) % mod)
	print(memo[N] * total[N] % mod)


import sys
from bisect import bisect_left as lb
from collections import deque
from queue import PriorityQueue as pq
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
mod = 10 ** 9 + 7
mx = 10 ** 6 + 10
ans = [0 for i in range(mx)]
ans[0] = 0
ans[1] = 1
(o, z) = (1, 0)
(o1, z1) = (0, 1)
(t, t1) = (2, 2)
flag = pow(2, mod - 2, mod)
for i in range(2, mx):
	(fl, fl1) = (o, z)
	o += o1
	z += z1
	o %= mod
	z %= mod
	o1 = fl
	z1 = fl1
	fl = t
	t = t * t1 % mod
	t1 = fl
	ans[i] = t * flag % mod * o % mod
for _ in range(ii()):
	n = ii()
	print(ans[n])


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07

def dfs(a, b, p, c):
	if a == b:
		return c
	for (i, j) in adj[a]:
		if i == p:
			continue
		temp = dfs(i, b, a, c + j)
		if dfs(i, b, a):
			mx = max(i, mx)
			return 1
	return tot
ans = [0] * 100005
ans[0] = 0
ans[1] = 1
(one, zero) = (1, 0)
(one1, zero1) = (0, 1)
(tt1, tt2) = (2, 2)
for i in range(2, 100004):
	(temp1, temp2) = (one, zero)
	one += one1
	one %= mod
	zero += zero1
	zero %= mod
	one1 = temp1
	zero1 = temp2
	temp = tt1
	tt1 = tt1 * tt2 % mod
	tt2 = temp
	ans[i] = tt1 * 500000004 % mod * one
	ans[i] %= mod

def hnbhai(tc):
	n = sb()
	print(ans[n])
for _ in range(sb()):
	hnbhai(_ + 1)


mod = 10 ** 9 + 7
fib = [(1, 0), (1, 1)]
for _ in range(10 ** 5):
	fib.append((2 * fib[-2][0] * fib[-1][0] % mod, (fib[-2][1] + fib[-1][1]) % mod))
for _ in range(int(input())):
	n = int(input())
	(val, uns) = fib[n]
	print(uns * val % mod)


MOD = 10 ** 9 + 7

def fib(n):
	f = [0, 1]
	pc = [1, 2]
	(a, b) = (0, 1)
	(c, d) = (1, 2)
	for i in range(2, n):
		(a, b) = (b, a + b)
		(c, d) = (d, c * d % MOD)
		f.append(b)
		pc.append(d)
	return (pc, f)
(PC, F) = fib(10 ** 5 + 2)

def calc3(n):
	(z, o) = (F[n - 1], F[n])
	j = o % MOD * PC[n + 1]
	if j & 1:
		j += MOD
	return j // 2 % MOD
for _ in range(int(input())):
	n = int(input())
	print(calc3(n))


from sys import stdin
input = stdin.readline
mod = 10 ** 9 + 7

def add(a, b):
	return (a % mod + b % mod) % mod

def mul(a, b):
	return a % mod * (b % mod) % mod

def div(a, b):
	return mul(a, pow(b, mod - 2, mod))

def pre():
	size = 10 ** 5 + 1
	for i in range(2, size):
		dp1.append(add(dp1[-1], dp1[-2]))
		dp.append(mul(dp[-1], dp[-2]))
		x = div(dp[-1], 2)
		ans.append(mul(dp1[-1], x))
ans = [0, 1]
dp1 = [0, 1]
dp = [2, 2]
pre()

def answer():
	return ans[n]
for T in range(int(input())):
	n = int(input())
	print(answer())