题目描述

瓜瓜在设计游戏关卡。游戏共有 $n$ 关，只能顺次尝试。第 $i$ 关有 $a_i$ 种通关方法，每过一关就可以得到一个徽章；或者选择放弃，跳到下一关但没有徽章。

如果两个完全通关玩家存在一关通过方法不同，那么称他们有不同的游戏路径。

瓜瓜特别喜欢某个质数 $p$ ，他希望设计的 $\{a_i\}$ 恰好使得，得到 $x(1 \leqslant x \leqslant n-1)$ 个徽章的所有可能的路径条数都能被 $p$ 整除。

如果限制 $1 \leqslant a_i \leqslant p - 1$ ，瓜瓜想知道有多少种满足要求的设计？答案可能很大，请对 $998244353$ 取模。

输入描述

第一行有一个整数 $T(1 \leqslant T \leqslant 1000)$ ，表示测试组数。

接下来 $T$ 行，每行有两个整数 $n, p$ ，其中 $1 \leqslant n < p \leqslant 10^6$ 。保证 $p$ 是质数。一共 $T$ 行，每行有一个数字。