背景

::::info[引言：其之三] :::align{center} $\textbf{启禁忌之\color{green}门扉}\textbf{，窥探真相。}$ ::: ::::

隙间的另一侧，既没有天空，也没有大地。

普通的魔法使骑着扫帚，如同流星一般从张开的隙间飞出。「拉普拉斯之眼」 在她身后一一闭合，最后的红光熄灭，隙间悄然合拢，在阴暗而无垠的空间中消失不见。

雾雨魔理沙用双手用力摁住扫帚，随即悬停在空旷的世界的中央。

——她的下方，有一扇由数字的光环围绕着的，紧闭的巨大「门扉」。

魔理沙迅速地认出了这扇来自「秘神」的禁忌之门。想必这正是秘神设下的机关，只要顺利通过，就能够窥探到异变背后的真相。

那么当下解决异变的关键一步，自然是找到这扇门的密码，打开它，然后前往它的背后——幕后黑手的巢穴。

魔理沙低头观察着光环上数字的跳跃与变幻。对于惯于搜刮遗迹与破解机关的魔法使而言，这样的挑战可是相当吸引人的。

「破译密码什么的，我魔理沙可擅长了 DA☆ZE。」

魔理沙抬起帽沿，开始认真观察这片地下迷径的运作规律。

题目描述

原始题面

光环上写有 $n$ 个数字，围绕着中央的门扉形成一个圆圈。魔理沙按顺序给每一个位置编了号，分别为 $1,2,\dots,n$。最开始，$i$ 号位置上写了一个数字 $a_i$，且 $a_1,\dots,a_n$ 是一个 $1 \sim n$ 的排列。

最开始光环上显示的数字就是门扉的密码。然而数字的排列在接下来的 $n$ 秒内发生了变化：在第 $i$ 秒，圆环上的第 $i$ 个位置亮起，它两侧的数字发生了交换。

魔理沙观察到，存在某一次交换，交换的两个数一个小于它们中间的数，一个大于它们中间的数。

借助这一条信息，魔理沙想知道这扇门有多少种可能的密码。

由于答案可能过大，魔理沙会告诉你一个大质数 $M$，让你回答答案对 $M$ 取模的结果。

形式化题意

一个环上有 $n$ 个点，编号分别为 $1,2,\dots,n$，其中 $i$ 与 $i+1$ 相邻，$n$ 与 $1$ 相邻。

每个点上有一个数字，点 $i$ 上的数字是 $p_i$，其中 $\{p_i\}$ 为 $1 \sim n$ 的一个排列。

依次对于 $i = 1,2,\dots,n$，交换与点 $i$ 相邻的两个点上的数字。

现在给定整数 $n,M$，求有多少个 $1 \sim n$ 的排列 $\{p_i\}$ 满足，在进行上述交换操作的过程中：

• 存在正整数 $i \in \{1,2,\dots,n\}$，设第 $i$ 次操作交换的两个点上的数字是 $a,b (a < b)$，则有 $a < p_i < b$（此处的 $p_i$ 指交换操作过程中点 $i$ 上的数字）。

答案对质数 $M$ 取模。

输入格式

本题有多组测试数据。

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

接下来 $T$ 行，每行两个整数 $n,M$，分别表示环上点数量和答案取模质数。

输出格式

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

6
4 100000007
19 100000037
318 100000039
2009 100000049
66666 100000073
114514 998244353

14
85972523
1253489
69168816
22857422
960610542

提示

样例解释

样例 #1 解释

以下是 $n=4$ 时符合要求的 $14$ 种排列：

• $(1,2,4,3)$；
• $(1,3,4,2)$；
• $(1,4,3,2)$；
• $(2,1,3,4)$；
• $(2,1,4,3)$；
• $(2,3,4,1)$；
• $(2,4,3,1)$；
• $(3,1,2,4)$；
• $(3,2,1,4)$；
• $(3,4,1,2)$；
• $(3,4,2,1)$；
• $(4,1,2,3)$；
• $(4,2,1,3)$；
• $(4,3,1,2)$。

数据范围

本题不采用捆绑测试。

此外，对于所有数据，$1 \le T \le 20, 3 \le n \le 10^6, 10^8 \le M < 10^9$，$M$ 是质数。