Palapa Number
Time limit2sMemory limit512 MB
Count N-digit numbers (no leading zero) where the first two digits sum to an even value or the last two digits form a prime, modulo 9973.
- Level
Medium6 of 10
- Topics
- Combinatorics, Math, Number theory, Dynamic programming
- Solved
- No attempts yet
Problem
A Palapa Number of N (4 <= N <= 100) is an N-digit decimal number such that the sum of its first two digits is even, or its last two digits form a prime number, or both. Leading zeros are not allowed.
For example,
- 1202 is a Palapa Number of 4, because it has 4 digits and its last two digits (02) form a prime number.
- 53160 is a Palapa Number of 5, because it has 5 digits and the sum of its first two digits (5 + 3 = 8) is even.
- 243913 is a Palapa Number of 6, because it has 6 digits, the sum of its first two digits (2 + 4 = 6) is even, and its last two digits (13) form a prime number.
- 0313 is not a Palapa Number.
- 460025 is not a Palapa Number.
Given N, output the number of Palapa Numbers of N, modulo 9973.
Input
The first line contains an integer T, the number of test cases. Each test case contains an integer N (4 <= N <= 100).
Output
For each test case, output the number of Palapa Numbers of N, modulo 9973.