C. 数三元图
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

"学霸题，数三元图。 $$$n$$$ 点有向图，点点一条边，图含三元环，共有多少图？"

以下是人话：

有一张 $$$n$$$ 个点的有向图，已知每两个点之间有且仅有一条有向边连接（对于任意两个点 $$$u,v(u \neq v)$$$ ，有且仅有 $$$u \rightarrow v$$$ 或是 $$$v \rightarrow u$$$ ），且该图包含至少一个三元环。问可能的图有多少种？你需要输出答案除以 $$$p$$$ 的余数。

Input

输入包含多组数据。

第一行一个整数 $$$T(1 \le T \le 10^4)$$$ ，表示数据的组数。

接下来 $$$T$$$ 行，每行两个正整数 $$$n,p$$$($$$1 \le n \le 10^6, 1 \le p \le 10^9$$$，不保证 $$$p$$$ 是质数) ，表示询问 $$$n$$$ 个点图中符合条件的图的数量除以 $$$p$$$ 的余数。

数据保证 $$$\sum n \le 5 \times 10^6$$$ 。

Output

对于每组数据，输出一行一个整数，表示符合条件的图的数量。

Example
Input
3
2 998244353
3 998244853
1000000 1
Output
0
2
0