题目背景

有一天，NaCly_Fish 无意间看到一种高效求阶乘模大质数的算法，但是她太菜，并不会写。
于是她就暴力造了数据，请您帮忙写出 std 吧。

什么，您问为什么不保证模数可以 NTT？
那样的话就可能被打表水过，或者答案就爆 int 了。

反正您是神仙，肯定能秒掉这题。

题目描述

给你正整数 $n$，和一个质数 $p$，你需要求出：

有 $T$ 组数据。

输入格式

第一行一个正整数 $T$，表示数据组数。
接下来 $T$ 行，每行两个正整数 $n,p$，意义如题目描述。

输出格式

输出 $T$ 行，表示每组数据的答案。

4
16777216 998244353
72267859 998244353
2333333 19260817
1919810 2147481811

789885751
569626621
16351109
1416439247

提示

数据范围：

对于 $10\%$ 的数据：$p = 998244353$
对于另外 $10\%$ 的数据：$p = 1004535809$
对于 $100\%$ 的数据：$1\le n < p \le 2^{31}-1$，$1 \le T \le 5$
保证 $p$ 为质数。

【提示】
请确保你的算法时间复杂度不高于 $\Theta(\sqrt n \log n)$，时限为 std 的十倍以上。