$n, m$ が与えられます。

$1 \leq a_i \leq m$ を満たす長さ $n$ の数列 $a_1, a_2, \dots, a_n$ のうち、任意の $1 \leq i < j \leq n$ に対して $\max\limits_{k=1}^i a_k = \min\limits_{k=j}^n a_k$ を満たさないようなものの個数を $998244353$ で割った余りを求めてください。

入力

1行目にテストケースの数 $T$ が与えられます。

続く $T$ 行の各行に、2つの正整数 $n, m$ が与えられます。

出力

$T$ 行にわたり、各データセットに対する答えを $998244353$ で割った余りを出力してください。

入出力例

入力 1

3
3 2
3 3
4 10

出力 1

2
12
7500

小課題

データセットの $50\%$ について、$n \leq 50$ を満たします。

すべてのデータセットについて、$1 \leq T \leq 10^5, 1 \leq n \leq 300, 1 \leq m \leq 10^9$ を満たします。