G. 迷宫 (II)
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

小 i 想知道，在一个长和宽都为 $$$2^n$$$ 的正方形网格上，利用迷宫 (I) 中所述的连边操作，一共可能产生多少种不同的连边结果？

我们定义，两种连边结果是不同的，当且仅当存在一条边，使得它在其中一个连边结果中出现，而在另一个连边结果中没有出现。

由于这个数字可能很大，因此请你输出它对一个给定正整数 $$$m$$$ 取模后的结果。

Input

第一行一个整数 $$$T$$$（$$$1 \leq T \leq 10^4$$$），表示一共有 $$$T$$$ 组数据。

对于每组数据：

  • 仅一行，包含两个整数 $$$n$$$ 和 $$$m$$$（$$$1 \leq n, m \leq 10^9$$$）。
Output

对于每组数据，输出一行，包含一个整数，表示答案。

Example
Input
6
1 1
1 10
2 10000
3 999999999
114514 1919810
999999999 998244353
Output
0
2
288
613014318
975328
98879783