Counting Matrices

Given a natural number $N$ and a prime $p$, let’s define a special set $Z_p = \{0, 1, 2, \dots, p-1\}$. Now count the number of different $N\times N$ invertible matrices where the entries of every matrices are from the set $Z_p$. That is the entries of the matrix are between $0$ to $p-1$ and all operations are done modulo $p$. To further elaborate this, a brief overview of the operations that can be performed are as follows:

1. Vector addition: let $x=[x_1\ x_2\ \dots\ x_N]^T$ and $y=[y_1\ y_2\ \dots\ y_N]^T$ be any two vectors of size $N\times 1$. Then we can add $x$ and $y$ as $x+y=[(x_1+y_1) \pmod{p}\ (x_2+y_2) \pmod{p}\ \dots\ (x_N+y_N)\pmod{p}]^T$.

2. Scalar multiplication: For any $x=[x_1\ x_2\ \dots\ x_N]^T$ and $a\in Z_p$, we can multiply $a$ with $x$ as $ax=[(ax_1)\pmod{p}\ (ax_2)\pmod{p}\ \dots\ (ax_N) \pmod{p}]^T$.

Similarly, since a $N\times N$ matrix is a ordered set of $N$column vector, we can say addition of two matrices, multiplication of a matrix by a scalar, and matrix multiplication will be done in similar fashion that the formula for each entry is evaluated modulo $p$.

Invertible matrix is one which has non zero determinant, equivalently it has N linearly independent rows/columns.

In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix $A$, denoted $det(A)$ which is calculated by the following procedure:

If the matrix is $1\times 1$, then $det(A)=a_{11}$. Otherwise for any $N\times N$ matrix, $det(A) = \left(\sum\limits_{m=1}^{m=N}(-1)^{m+1}a_{ij}det(A_{ij})\right)\pmod{p}$. Here, $a_{ij}$ is the entry of $i^{th}$ row and $j^{th}$ column of the matrix, and $A_{ij}$ is the $(N-1)\times (N-1)$matrix obtained by removing the $i^{th}$ row and $j^{th}$ column of $A$.

A set of vectors (row/column) $B= \{v_1, v_2, \dots, v_N\}$ is called linearly independent when $\sum\limits_{m =1}^{N}a_mv_m = 0$ if and only if $a_m=0$ for all $m\in\{1, 2, \dots, N\}$is true. For example: $v_1=[1\ 1], v_2=[-1\ -1]$ are not linearly independent as $v_1+v_2=0$thus $a_1=a_2=1$also makes the sum $0$.

Input

First line of the input contains an integer $T (0< T <101)$ denoting the number of test cases to be followed. Each of the next $T$ lines contain two integers $N (1<N<1000001)$ and $p (1<p<10000001)$. You need to count the number of $N\times N$invertible matrices with entries from $Z_p$. You are guaranteed that the $p$ in input is a prime number.

Output

For each case, print the number of $N\times N$invertible matrices in the given setup in a separate line. Since the numbers can be pretty big, print your answer modulo $998244353$.

Sample

2
2 3
2 2

48
6

In sample input of 2 2, the valid matrices are the following:

$\begin{bmatrix}1 & 0 \\ 0 & 1 \end{bmatrix}$, $\begin{bmatrix}0 & 1 \\ 1 & 0 \end{bmatrix}$, $\begin{bmatrix}1 & 1 \\ 1 & 0 \end{bmatrix}$, $\begin{bmatrix}1 & 1 \\ 0 & 1 \end{bmatrix}$, $\begin{bmatrix}0 & 1 \\ 1 & 1 \end{bmatrix}$, $\begin{bmatrix}1 & 0 \\ 1 & 1 \end{bmatrix}$.