This problem is very simple; it doesn't even have a background story. But to help you understand the problem smoothly, the kind Yazid will introduce some concepts to you:

• Simple graph: A graph with no multiple edges or self-loops. (Multiple edges are two identical edges, and a self-loop is an edge whose endpoints are the same vertex.)
• Complement graph: The complement graph of a graph $G$ has the exact same vertices as $G$, and there is an edge between any two vertices if and only if they are not adjacent in $G$.

We inductively define an undirected simple graph to be good:

1. A single vertex is good.
2. A graph formed by several good graphs as its connected components is good.
3. The complement graph of a good graph is good.

Given a positive integer $n$.

Find the number of non-isomorphic good graphs with $n$ vertices modulo a prime $P$. (Here, $P$ is a constant, see the Input section for details.)

Two good graphs are considered non-isomorphic (essentially different) if and only if no matter how one graph is relabeled, it cannot be made identical to the other graph.

Input

The input contains multiple test cases. The first line contains two space-separated integers $T$ and $P$, representing the number of test cases and the modulo, respectively.

Then, the test cases are described in order. For each test case:

• A single line containing an integer $n$, representing the number of vertices of the good graphs to be counted.

Output

For each test case, output one line:

• An integer, representing the number of good graphs with $n$ vertices modulo $P$.

Examples

Input 1

2 233
3
4

Output 1

4
10

Note

Below are all the good graphs with 3 vertices:

Constraints

It is guaranteed that $T \le 233$, $n \le 23333$, $2^{29} < P < 2^{30}$, and $P$ is guaranteed to be a prime number.

Hints

The time complexity of the algorithm that can pass this problem might be worse than you think, or it might be better than you think.