16179번 - 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.

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).

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