Chloe is fascinated by prime numbers. She came across the number on a sign and, though the number is not prime, found some primes hiding in it by using the following rules:
- Every three consecutive digits sum to a prime:
- Every four consecutive digits sum to a prime:
- Every five consecutive digits sum to a prime:
You must answer queries, where each query consists of an integer, . For each , find and print the number of positive -digit numbers, modulo , that satisfy all three of Chloe's rules (i.e., every three, four, and five consecutive digits sum to a prime).
Input Format
The first line contains an integer, , denoting the number of queries.
Each of the subsequent lines contains an integer denoting the value of for a query.
Constraints
Output Format
For each query, print the number of -digit numbers satisfying Chloe's rules, modulo , on a new line.
Sample Input 0
1
6
Sample Output 0
95
Explanation 0
There are six-digit numbers satisfying the property above, where the respective first and last ones are and .