Patlu has recently got a new problem based on Pallindromes. A Pallindrome is a number that is same from front and back, example $121$ is pallindrome but $123$ is not . He wants to calculate sum of all $N$ digit number which are Pallindromic in nature and divisible by $9$ and does not contain any zero in their decimal representation. As the answer can be very large so print the sum modulo $10^9 + 7$.

-----Input:-----
- First line of input contain $T$, number of testcases. Then the testcases follow.
- Each testcase contains single line of input , one integer $N$.

-----Output:-----
- For each testcase, output in a single line answer having $N$ digits pallindromic string.

-----Constraints-----
- $1\leq T \leq 100$
- $1\leq N \leq 10^5$

-----Sample Input:-----
2
1
2

-----Sample Output:-----
9
99

Difficulty: interview

Starter code:

Solutions:
def getsum(N):
	if N==1:
		return 9
	if N==2:
		return 99
	s = ""
	for i in range(0,N):
		s = s+'5'
	s = int(s)
	if N%2==0:
		s = s*pow(9,N//2-1)
	else:
		s = s*pow(9,N//2)
	return s%(pow(10,9)+7)

def main():
	t = int(input())
	for _ in range(0,t):
		N = int(input())
		result = getsum(N)
		print(result)
def __starting_point():
	main()

__starting_point()