题目背景

题目描述

给定 $n,m$ 两个正整数，构造无重边无自环的一张连通无向图，共 $n$ 个结点和 $m$ 条边权分别为 $1\sim m$ 的边，使得其最小生成树的边权和最大。

你只需要输出最小生成树的边权和对 $998244353$ 取模的值即可。

输入格式

本题有多组测试数据。

第一行输入一个正整数 $T$，表示测试数据组数。

对于每组测试数据，共一行两个正整数 $n,m$。

输出格式

共 $T$ 行，对于每组数据输出最小生成树的边权和对 $998244353$ 取模的值即可。

3
4 6
4 5
5 8

7
7
14

说明/提示

样例解释

对于样例一中的第一组测试数据，构造如下：

此时答案为 $1+2+4=7$。

输入样例 #2

20
22 106
16 25
27 34
8 18
17 57
5 6
8 13
4 5
8 24
25 185
30 162
14 44
22 94
7 7
4 4
29 356
14 28
26 130
12 23
11 27

输出样例 #2

1190
230
529
59
502
13
50
7
63
2074
2711
299
1101
25
7
3659
216
1830
146
141

输入样例 #3

20
4 6
18 119
25 32
15 65
7 17
26 157
22 181
4 6
14 19
21 134
10 18
6 12
5 5
19 167
11 51
25 290
30 208
14 16
16 22
8 17

输出样例 #3

7
812
462
423
41
2061
1520
7
149
1226
91
25
12
987
175
2324
3186
122
200
58

数据范围

本题采用捆绑测试。

对于 $100\%$ 的测试数据，满足 $1\le T \le 10^6$，$4\le n\le m\le 10^{18}$，$m\le \frac{n\times(n-1)}{2}$。