Note: The time limit for this problem is $10$ seconds per $1$ case.

Problem Statement

You are given positive integers $T$ and $M$. Then, $T$ test cases are given. Solve the following problem for each of them.

For a permutation $P$ of $(1,2,...,N)$, let the score $f(P)$ be the number of distinct permutations that can be obtained by repeating the operation described below 0 or more times.

Below, the $i \,(1 \leq i \leq N)$-th element of the permutation $P$ is denoted by $P_{i}$.

• In each operation, choose one of the following 2 procedures and perform it.

  • Replace $P$ with the permutation $R$ of $(1,2,...,N)$ satisfying $P_{R_i} = i$ for all $i = 1,2,...,N$.
  • Replace $P$ with the permutation $R$ of $(1,2,...,N)$ satisfying $R_{i} = P_{N - i + 1}$ for all $i = 1,2,...,N$.

There are $N!$ possible permutations $P$ of $(1,2,...,N)$. Find the sum of their scores $f(P)$, modulo $M$.

Constraints

• $1 \leq T \leq 10^6$
• $1 \leq N \leq 5 \times 10^6$
• $1 \leq M \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format.

$T$ $M$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Here, $\mathrm{case}_i$ denotes the $i$-th test case.

Each test case is given in the following format.

$N$

Output

Print the answers over $T$ lines.

On the $i \,(1 \leq i \leq T)$-th line, print the answer to the $i$-th test case.

Sample

3 998244353
3
1
4478429

20
1
722594001