We consider 2D arrays $A$, (0,0)-indexed, shape $N \times M$.
With $0 \le i < N$ and $0 \le j < M$, we have $0< A_{i,j} \le N \times M$.
Our interest will be to count those arrays that have the two properties :

• Arrays $A$ are composed with all numbers from $1$ to $N \times M$.
  i.e. we have $(i,j) \neq (k,l) \implies A_{i,j} \neq A_{k,l}$
• $(i\oplus j) > (k\oplus l) \implies A_{i,j} > A_{k,l}$, where $\oplus$ denotes bitwise XOR.

Input

The first line contains $T$, the number of test cases, and $P$ a prime number.

Each of the next $T$ lines contains $N$ and $M$, the shape of the arrays $A$.

Output

For each test case, print the number of arrays $A$ with the given properties.
As the result may be large, the answer modulo $P$ is required.

Example

Input:
2 1000000007
2 2
997 799

Output:
4
828630475

For the first case, the 4 possible 2x2 arrays are : $\binom{1\; 3}{4\; 2}$, $\binom{1\; 4}{3\; 2}$, $\binom{2\; 3}{4\; 1}$, and $\binom{2\; 4}{3\; 1}$.

Constraints

$1 \le T \le 10^4$,
$10^9 < P < 2\times 10^9$, a prime number,
$1 \le N \le 10^9$,
$1 \le M \le 10^5$.

Constraints allow a small kB of unoptimized PY3.4 code to get AC in the third of the TL. Have fun.