시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 5 5 5 100.000%

## 문제

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.

## 예제 입력 1

2
4
5


## 예제 출력 1

5625
6385