SP18799 BORING2 - Boring Factorials (Extended)

给定 $N,P$，求 $N!\bmod P$。保证 $|N-P|\leq 10^6$。

多组数据。第一行输入一个整数 $T$ 表示数据组数。 接下来 $T$ 行每行两个整数 $N,P$，代表一组数据。

每组数据输出一行一个整数，表示答案。

$1\leq T