题目描述

已知两个正整数 $a,b$ 满足 $a+b=m$，求 $(a!+b)\bmod p$ 的最大值，其中 $m,p$ 给定。

你需要在 $40\operatorname{MiB}$ 的空间限制和 $2\operatorname{s}$ 的时间限制下解决 $T$ 个这样的问题。

输入格式

第一行输入一个正整数 $T$，表示问题个数。

第 $i+1\ (1\le i\le T)$ 行，每行输入两个整数 $m,p$，表示第 $i$ 个问题。

输出格式

输出 $T$ 行，第 $i\ (1\le i\le T)$ 行输出一个整数，表示第 $i$ 个问题的答案。

2
3 5
4 7

3
4

提示

样例解释

对于第 $1$ 个问题，有 $a=1,b=2$ 或 $a=2,b=1$，此时 $(a!+b) \bmod p=3$。

对于第 $2$ 个问题：

• 如果 $a=1,b=3$，那么 $(a!+b)\bmod p=4$；
• 如果 $a=2,b=2$，那么 $(a!+b)\bmod p=4$；
• 如果 $a=3,b=1$，那么 $(a!+b)\bmod p=0$；

所以答案是 $4$。

数据范围

对于所有测试数据，保证：

• $1\le T\le 10^6$；
• $2\le m\le p\le 10000$。

::cute-table{tuack} |测试点编号|$p\le$|$T\le$| |:-:|:-:|:-:| |$1$|$10$|$45$| |$2$|$100$|$4950$| |$3,4$|$10000$|$1000$| |$5,6$|$3000$|$10^6$| |$7\sim10$|$10000$|^|