- Prepare
- Algorithms
- Dynamic Programming
- Prime Digit Sums

# Prime Digit Sums

# Prime Digit Sums

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 .