Palapa Number

Palapa Number of N (4 ≤ N ≤ 100) is an N digits decimal number where the sum of the first two digits is even, or the last two digits is a prime number, or both. No leading zero allowed.

For example,
1202 is Palapa Number of 4, because it has 4 digits and the last two digits (02) is a prime number.
53160 is Palapa Number of 5, because it has 5 digits and the sum of the first two digits (5 + 3 = 8) is an even number.
243913 is Palapa Number of 6, because it has 6 digits, the sum of the first two digits (2 + 4 = 6) is an even number, and the last two digits (13) is a prime number.
0313 is not Palapa Number.
460025 is not Palapa Number.

Given N, output the number of Palapa Number of N, modulo by 9973.

Input

The first line of input contains an integer T, the number of test cases follow.

Each test case contains an integer N (4 ≤ N ≤ 100).

Output

For each test case, output the number of Palapa Number of N exists modulo by 9973.


Input
2
4
5
Output
5625
6385