【模板】快速阶乘算法

有一天，NaCly_Fish 无意间看到一种高效求阶乘模大质数的算法，但是她太菜，并不会写。 于是她就暴力造了数据，请您帮忙写出 std 吧。 什么，您问为什么不保证模数可以 NTT？ 那样的话就可能被打表水过，或者答案就爆 int 了。 反正您是神仙，肯定能秒掉这题。

给你正整数 $n$，和一个质数 $p$，你需要求出： $$ n! \text{ mod } 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 的十倍以上。