U468993 【模板】QYC 分治

如果你是从 [$\color{black}\text{CYQ 分治}$](https://www.luogu.com.cn/problem/U460754)过来的那么你大概是发现彩蛋了 CYQ 发明了 $\log n$ 计算阶乘算法但是带着亿点常数，所以 CYQ 发明了 QYC 分治优化多余的常数。 [$\color{white}\text{当然也可以考虑}$](https://florr.io)[$\color{white}\text{多重 CYQ 分治。}$](https://www.luogu.com.cn/problem/U469475)

CYQ 认为任何人都可以 $\log n$ 计算阶乘且只有极小的常数，所以让你给 CYQ 分治计算阶乘代码增加 QYC 分治。

第一行一个正整数 $q$。 接下来 $q$ 行，每行两个数 $n,p$，请你计算 $n! \bmod p$。

$q$ 行，每行一个整数，表示 $n! \bmod p$。

QYC 分治优化 [$\color{black}\text{CYQ 分治}$](https://www.luogu.com.cn/problem/U460754)。 对于 $100\%$ 的数据，保证 $q \le 2 \times 10^4，1 \le n \le 2^{31}-1$，且 $p$ 为质数。 记得重复进行一致的操作。 已开启 Special Judge，你的答案与标准答案的绝对误差应小于固定常数 $k$。$\color{white}\text{k=1000000000000000000}。$