题目描述

对于一个数列 $q$，记 $q_i$ 为数列中第 $i$ 个数的值。现在有一个数列 $a$，称作初始数列。已知 $a$ 为一个 $n$ 阶排列，你需要通过一种特殊的方法将初始序列重排得到 $b$。这个方法需要两个栈 $s1,s2$，每次你可以在下面的三个操作（如果可行）中选择一个执行直到 $a,s1,s2$ 均为空：

1. 若数列 $a$ 非空，则将 $a$ 末尾的数移入 $s1$ 作为栈顶。

2. 若栈 $s1$ 非空，则将 $s1$ 的栈顶移入 $s2$ 作为栈顶。

3. 若栈 $s2$ 非空，则将 $s2$ 的栈顶移入数列 $b$ 作为开头。

由于一些原因，任意时刻若栈 $s1$ 非空，要满足 $s1$ 中的元素从栈底到栈顶递减。最终你的目标是使得数列 $b$ 递增。 可是你发现对于某一些特定的初始数列，无论如何操作都无法达成目标，求有多少个初始 $n$ 阶数列无法达成目标。

这个问题有些复杂，于是你只需要输出每个问题的答案对一个质数 $p$ 取模后的结果。

输入格式

从文件 sort.in 中读入数据。

第一行一个整数 $T$ 表示数据组数。

接下来 $T$ 行，每行两个整数 $n,p$ 表示一个问题的参数。

输出格式

输出到文件 sort.out 中。

共 $T$ 行，每行一个整数表示答案。

样例 1 输入

3
4 998244353
5 998244353
12 998244353

样例 1 输出

2
30
473708154

样例 1 解释

对于 $n = 4$ 的其中一种初始数列 $[3, 4, 1, 2]$ 可以通过下面的步骤排序，因此不计入答案：

1. $\color{red}{\text{操作 1}}$：把 $2$ 从数列 $a$ 移入 $s1$ 作为栈顶，此时 $s1$ 从栈底数起依次是 $2$；

2. $\color{red}{\text{操作 1}}$：把 $1$ 从数列 $a$ 移入 $s1$ 作为栈顶，此时 $s1$ 从栈底数起依次是 $2, 1$；

3. $\color{orange}{\text{操作 2}}$：把 $1$ 从 $s1$ 移入 $s2$ 作为栈顶，此时 $s1$ 从栈底数起依次是 $2，s2$ 从栈底数起依次是 $1$；

4. $\color{orange}{\text{操作 2}}$：把 $2$ 从 $s1$ 移入 $s2$ 作为栈顶，此时 $s1$ 变为空，$s2$ 从栈底数起依次是 $1, 2$；

5. $\color{red}{\text{操作 1}}$：把 $4$ 从数列 $a$ 移入 $s1$ 作为栈顶，此时 $s1$ 从栈底数起依次是 $4$；

6. $\color{orange}{\text{操作 2}}$：把 $4$ 从 $s1$ 移入 $s2$ 作为栈顶，此时 $s1$ 变为空，$s2$ 从栈底数起依次是 $1, 2, 4$；

7. $\color{blue}{\text{操作 3}}$：把 $4$ 从 $s2$ 移入数列 $b$ 作为开头，此时 $s2$ 从栈底数起依次是 $1, 2$；

8. $\color{red}{\text{操作 1}}$：把 $3$ 从数列 $a$ 移入 $s1$ 作为栈顶，此时 $s1$ 从栈底数起依次是 $3$；

9. $\color{orange}{\text{操作 2}}$：把 $3$ 从 $s1$ 移入 $s2$ 作为栈顶，此时 $s1$ 变为空，s2 从栈底数起依次是 $1, 2, 3$；

10. $\color{blue}{\text{操作 3}}$：把 $3$ 从 $s2$ 移入数列 $b$ 作为开头，此时 $s2$ 从栈底数起依次是 $1, 2$；

11. $\color{blue}{\text{操作 3}}$：把 $2$ 从 $s2$ 移入数列 $b$ 作为开头，此时 $s2$ 从栈底数起依次是 $1$；

12. $\color{blue}{\text{操作 3}}$：把 $1$ 从 $s2$ 移入数列 $b$ 作为开头，此时 $s2$ 变为空；

最终数列 $b$ 递增。

样例 2、3

大样例

测试点约束

对于所有测试点，$1 \leq T \leq 5，1 \leq n \leq 5 \times 10^6，10^8 \leq p \leq 1.1 \times 10^9$，保证 p 是质数。

每个测试点的具体限制见下表：