import operator


ZERO = int(False)
ONE = int(True)
TWO = sum([ONE,ONE])
SEVEN = sum([ONE,ONE,ONE,ONE,ONE,ONE,ONE])
NINE = sum([ONE,ONE,ONE,ONE,ONE,ONE,ONE,ONE,ONE])
TEN = sum([ONE,ONE,ONE,ONE,ONE,ONE,ONE,ONE,ONE,ONE])

mod = operator.add(pow(TEN, NINE), SEVEN)


def mat_mul(ma, mb):
	ret = [[ZERO,ZERO],[ZERO,ZERO]]
	for i in range(TWO):
		for k in range(TWO):
			for j in range(TWO):
				ret[i][j] = operator.mod(operator.add(ret[i][j], operator.mul(ma[i][k], mb[k][j])), mod);
	return ret


def mat_pow(x, p):
	ret = [[ONE,ZERO],[ZERO,ONE]]

	while (p):
		if p & ONE:
			ret = mat_mul(ret, x)
		x = mat_mul(x, x)
		p = p >> ONE
	return ret


def solve(n):
	if n == ONE:
		return ONE
	mat = [[ONE,ONE],[ONE,ZERO]]
	mat = mat_pow(mat, operator.sub(n, ONE))
	return operator.mod(operator.add(mat[ZERO][ZERO], operator.mul(mat[ZERO][ONE], TWO)), mod)


t = int(input())

for i in range(t):
	n = int(input())
	print(solve(n))