In this problem, for an undirected graph without multiple edges or self-loops, a path is called a simple path if and only if it does not visit any node more than once. That is, if the sequence of nodes visited by the path is $(u_1, u_2, \dots, u_k)$, the path is a simple path if and only if $u_1, u_2, \dots, u_k$ are all distinct.

Given a large prime $P$ and $q$ queries, each query provides a positive integer $n$. You need to find the number of labeled undirected graphs satisfying all the following conditions, modulo $P$:

1. The graph has $n$ nodes and contains no multiple edges or self-loops;
2. There is no simple path of length 3 in the graph, i.e., there do not exist four distinct nodes $u_1, u_2, u_3, u_4$ such that $(u_1, u_2), (u_2, u_3), (u_3, u_4)$ are all edges in the graph;
3. Subject to conditions 1 and 2, the number of edges in the graph is maximized.

Input

The first line contains two positive integers $q$ and $P$, where $q \le 10^5$ is the number of queries and $P$ is the modulus.

Each of the next $q$ lines contains a positive integer $n$, where $n \le 3 \times 10^7$, describing a query.

Output

For each query, output a single non-negative integer representing the number of labeled undirected graphs satisfying the conditions, modulo $P$.

Examples

Input 1

2 199932539
1
6

Output 1

1
10

Note 1

The following explanation uses integers from $1$ to $n$ to label each node.

For the first query, only the graph with an empty edge set $\varnothing$ satisfies the conditions.

For the second query, two examples of graphs satisfying the conditions have edge sets $\{(1,2), (2,3), (1,3), (4,5), (5,6), (4,6)\}$ and $\{(1,3), (3,5), (1,5), (2,4), (4,6), (2,6)\}$.

Subtasks

For all test cases, $10^8 < P < 10^9$ and $P$ is a prime number.