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.