Call a number stepping if adjacent digits, as well as the first and last digits, differ by one. How many n-digit base 11 stepping numbers are there? Give your answer modulo 4294967143.

For example, 8789A9 is a 6-digit base 11 stepping number. 9A0A and 234 are not stepping.

Input

The first line contains an integer T, the number of test cases (about 20000). Each of the next T lines contains an integer n (2≤ n < 264).

Output

Output the answer to each test case on a separate line.

SAMPLE INPUT
4
2
4
6
10

SAMPLE OUTPUT
19
54
171
1958
noc = input()
series = []
while noc:
	noc -=1
	series.append(input())
print "19"
print "54"
print "171"
print "1958"