题目描述

这里有一个与森林（一种特殊的图）相关的问题。在向你介绍该问题之前，我们先给出本题中使用的一些定义。一个具有 $n$ 个顶点的带标号森林是一张无环的无向简单图，其中的顶点由 $1, 2, \cdots, n$ 标号。若两张带标号森林的顶点数不同，或者当顶点数相同时，存在某个标号 $i$ 使得这两张森林中标号为 $i$ 的顶点的邻居具有不同的标号（即这两张森林里标号为 $i$ 的顶点的所有邻居的标号集合不同），则这两张带标号森林被视为不同。

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

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

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

更确切地说，如果期望值的既约分数为 $\frac{p}{q}$，你需要提供最小的非负整数 $r$，使得 $q r \equiv p \pmod{998244353}$。

输入格式

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

对于每组测试数据，仅有一行包含两个整数 $n$ 和 $m$，满足 $1 \leq n \leq 2 \times 10^5$，$n \leq m \leq 998244352$。

我们保证每组测试数据中 $q$ 的模意义下的乘法逆元总是存在的，换句话说，所有测试数据均保证 $q \not \equiv 0 \pmod{998244353}$。

输出格式

对于每组测试数据，输出一行包含对 $998244353$ 取模后的答案。

4
1 1
2 3
3 7
4 16

0
5
66
576

提示

翻译由 DeepSeek V4 Pro 完成