問題文

$N$ 頂点からなる完全グラフがあります。
このグラフの $M=N(N-1)/2$ 本の辺は $i=1,2,\dots,M$ と番号付けられ、互いに区別されます。

最初、$M$ 本の辺は全て白色です。
あなたは $M$ 本の辺の中から一部を選び、それぞれ赤・青・紫のいずれかの色で塗ります（ $1$ 本の辺を複数の色で塗ることはできません）。
次の条件を全て満たす塗り分け方は何通りあるでしょうか。

• 赤・青・紫の辺の数はそれぞれ $N-1-K,N-1-K,K$ であり、残りの辺は白色のままである。
• 赤または紫の $N-1$ 本の辺のみを残して得られるグラフは木である。
• 青または紫の $N-1$ 本の辺のみを残して得られるグラフは木である。

なお、ある $2$ つの塗り分け方において色が異なる辺 $i\ (1\le i \le M)$ が $1$ 本以上存在するとき、それらの塗り分け方は異なるとみなします。
答えは非常に大きくなることがあるので、$998244353$ で割った余りを求めてください。

一つの入力につき、$T$ 個のテストケースに答えてください。

制約

• $1 \le T \le 5\times 10^5$
• $2 \le N \le 2000$
• $0 \le K \le N-1$
• 入力は全て整数である。

入力

まず $1$ 行目に、入力に含まれるテストケースの数 $T$ が与えられます。

$T$

その後、$T$ 行にわたって $T$ 個のテストケースが与えられます。各テストケースは次の形式で $1$ 行で与えられます。

$N\ \ K$

出力

$T$ 行出力してください。
$i$ 行目 $(1\le i \le T)$ には、$i$ 番目のテストケースに対する回答を出力してください。

サンプル

12
2 0
2 1
3 0
3 1
3 2
4 0
4 1
4 2
4 3
10 9
314 159
1883 1014

0
1
0
6
3
12
120
108
16
100000000
771532131
812345678