Bricks

Wiktor and Hektor, having finished their game, moved on to something more productive: helping build their neighbor's summer cottage.

A delivery of $N$ bricks has just arrived at the construction site, and the boys must divide it into smaller piles. They begin together, splitting the single whole pile into two smaller piles. After that each boy works on his own, and every one of his moves takes one existing pile and splits it into two smaller, non-empty piles.

When the boys stop for a break, they notice with surprise that:

• Each of them made exactly the same number of independent splits.
• The number of bricks in every resulting pile is a prime number.

How many different final arrangements of piles could they have reached? Two arrangements are considered different if, for some pile size, one arrangement contains more piles of that size than the other (in other words, an arrangement is identified by the multiset of its pile sizes).

The first line contains the number of test cases $Z$ ($1 \le Z \le 10$).

The second line contains a single integer $M$ ($2 \le M \le 10^7$), the modulus.

Each of the next $Z$ lines contains a single integer $N$ ($2 \le N \le 20000$), the number of bricks delivered in that test case.

For each test case, print on its own line the number of different valid pile arrangements for $N$ bricks, taken modulo $M$.

When $N = 5$, the only possibility is the initial joint split into piles of $2$ and $3$ (both prime), with no independent splits afterwards, so the answer is $1$.

When $N = 8$ there are two possibilities:

1. the boys split the pile into $3$ and $5$ (both prime) and make no independent splits;
2. the boys split the pile into $4$ and $4$, and then each boy splits one pile of $4$ into two piles of $2$, ending with piles $2, 2, 2, 2$.

So the answer is $2$.