Given a natural number N and a prime p, let’s define a special set Zp={0,1,2,…,p−1}. Now count the number of different N×N invertible matrices where the entries of every matrices are from the set Zp. 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:
Vector addition: let x=[x1x2…xN]T and y=[y1y2…yN]T be any two vectors of size N×1. Then we can add x and y as x+y=[(x1+y1)(modp)(x2+y2)(modp)…(xN+yN)(modp)]T.
Scalar multiplication: For any x=[x1x2…xN]T and a∈Zp, we can multiply a with x as ax=[(ax1)(modp)(ax2)(modp)…(axN)(modp)]T.
Similarly, since a N×N matrix is a ordered set of Ncolumn 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×1, then det(A)=a11. Otherwise for any N×N matrix, det(A)=(m=1∑m=N(−1)m+1aijdet(Aij))(modp). Here, aij is the entry of ith row and jth column of the matrix, and Aij is the (N−1)×(N−1)matrix obtained by removing the ith row and jth column of A.
A set of vectors (row/column) B={v1,v2,…,vN} is called linearly independent when m=1∑Namvm=0 if and only if am=0 for all m∈{1,2,…,N}is true. For example: v1=[11],v2=[−1−1] are not linearly independent as v1+v2=0thus a1=a2=1also 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×Ninvertible matrices with entries from Zp. You are guaranteed that the p in input is a prime number.
Output
For each case, print the number of N×Ninvertible matrices in the given setup in a separate line. Since the numbers can be pretty big, print your answer modulo 998244353.
Sample
Input
Output
2
2 3
2 2
48
6
In sample input of 2 2, the valid matrices are the following: