这是一个关于森林（一种特殊的图）的问题。在介绍问题之前，我们先给出本题中使用的一些定义。一个具有 $n$ 个顶点的带标号森林是一个无环无向简单图，其顶点标号为 $1, 2, \dots, n$。如果两个带标号森林的顶点数不同，则它们被视为不同；如果顶点数相同，但对于某些整数 $i$，这两个森林中标号为 $i$ 的顶点的邻居集合不同（即标号为 $i$ 的顶点的所有邻居的标号集合不同），则它们也被视为不同。

树状结构在计算机编程中随处可见，这是 Bob 见过的最迷人的事物。今天，Bob 想要从所有可能的具有 $n$ 个顶点的带标号森林中等概率地随机选择一个森林 $G$。然后，如果顶点 $i$ 到顶点 $j$ 之间存在最短路径，他将 $\delta(i, j)$ 设为该最短路径上的边数；否则，他将 $\delta(i, j)$ 设为 $m$。Bob 对以下表达式的期望值感到好奇：

$$\sum_{i=1}^{n} \sum_{j=i+1}^{n} \delta^2(i, j)$$

但这对他来说太难了。你能帮 Bob 求出该期望值对 $998244353$ 取模的结果吗？

更准确地说，如果期望值的最简分数形式为 $\frac{p}{q}$，你需要提供满足 $qr \equiv p \pmod{998244353}$ 的最小非负整数 $r$。

输入格式

输入包含多个测试用例。第一行包含一个正整数 $T$，表示测试用例的数量，最多为 $2 \times 10^5$。

对于每个测试用例，仅一行包含两个整数 $n$ 和 $m$，其中 $1 \le n \le 2 \times 10^5$ 且 $n \le m \le 998244352$。

我们保证在每个测试用例中 $q$ 的模逆元总是存在，换句话说，保证在所有测试用例中 $q \not\equiv 0 \pmod{998244353}$。

输出格式

对于每个测试用例，输出一行，包含答案对 $998244353$ 取模的结果。

样例

样例输入 1

4
1 1
2 3
3 7
4 16

样例输出 1

0
5
66
576