P17472 [ICPC 2018 Jiaozuo R] Shortest Paths on Random Forests

Here is a problem related to forest, which is a special type of graph. Before introducing this problem to you, we intend to show some definitions used in this problem. A labelled forest with $n$ vertices is an acyclic undirected simple graph in which vertices are labelled by $1, 2, \cdots, n$. Two labelled forests are regarded as different if their numbers of vertices are different or, if they have the same number of vertices, for some integers $i$ and for vertices labelled by $i$ in these two forests, their neighbours have different labels (which means that the sets of labels corresponding to all neighbours of vertices labelled by $i$ in these two forests are different). Tree-like structures are constructed in computer programming constantly, which is the most fascinating part Bob has ever seen. Today, Bob wants to randomly choose a labelled forest $G$ from all possible labelled forests having $n$ vertices with equal probability. Then, he will set $\delta(i, j)$ to the number of edges on the shortest path from the vertex labelled $i$ to the vertex labelled $j$ if the shortest path exists, or set $\delta(i, j)$ to $m$ otherwise. Bob is curious about the expected value of $$\displaystyle \sum_{i = 1}^{n}{\sum_{j = i + 1}^{n}{\delta^2(i, j)}},$$ but it's hard for him. Can you help Bob find out the expected value modulo $998244353$? More precisely, if the reduced fraction of the expected value is $\frac{p}{q}$, what you should provide is the minimum non-negative integer $r$ such that $q r \equiv p \pmod{998244353}$.

The input contains several test cases, and the first line contains a positive integer $T$ indicating the number of test cases which is up to $2 \times 10^5$. For each test case, the only one line contains two integers $n$ and $m$ where $1 \leq n \leq 2 \times 10^5$ and $n \leq m \leq 998244352$. We guarantee that the modular multiplicative inverse of $q$ in each test case always exists, in other words, the condition $q \not \equiv 0 \pmod{998244353}$ is guaranteed to be true in all test cases.

For each test case, output a line containing the answer modulo $998244353$.