問題文

富士山の周囲には、1,2,\ldots,N の番号が付いた N 個の地域が、番号順に円環状に並んでいます。 すなわち、1\leq i \lt N に対して地域 i と地域 i+1 は隣り合い、地域 N と地域 1 も隣り合っています。

画家である jastaway 君は、これらの地域と富士山を題材にした 「富岳 NK 景」 という絵画のシリーズを制作しました。

このシリーズには、1\leq s\leq N,\ 1\leq d\leq K を満たす整数の組 (s,d) ごとに 1 枚、合計 NK 枚の絵画があります。 (s,d) に対応する絵画には、地域 s から番号の増加する向きに並ぶ連続した d 個の地域が描かれています。 地域の番号は円環状に考え、地域 N の次は地域 1 とします。例えば N=6 のとき、(5,4) に対応する絵画には、地域 5,6,1,2 が描かれています。

各絵画について、その絵画に描かれているすべての地域に、その絵画のレプリカが 1 枚ずつ保存されています。

富士山が好きな tatesoto 君は、富岳 NK 景のすべての絵画のレプリカを 1 枚ずつ集めることにしました。 そのために、N 個の地域をそれぞれちょうど 1 回訪れます。地域を訪れる順番は自由に決めることができます。

はじめ、tatesoto 君はどの絵画のレプリカも持っていません。tatesoto 君が地域 i を訪れると、その地域に保存されているレプリカのうち、まだ持っていない絵画のレプリカをすべて 1 枚ずつ受け取ります。地域 i で tatesoto 君が受け取るレプリカの枚数を C_i とします。

地域を訪れる順番を自由に決めたとき、整数列 (C_1,C_2,\ldots,C_N) として何通りの異なる列が得られるかを求めてください。ただし、2 つの整数列 (C_1,C_2,\ldots,C_N) と (C'_1,C'_2,\ldots,C'_N) が異なるとは、C_i \neq C'_i を満たす整数 i (1 \leq i \leq N) が存在することをいいます。

答えは非常に大きくなる可能性があるため、998244353 で割ったあまりを出力してください。

T 個のテストケースについて答えてください。

制約

• 1 \le T \le 10^5
• 2 \le N \le 2 \times 10^5
• 1 \le K \le N-1
• すべてのテストケースについての N の総和は 2 \times 10^5 以下
• 入力される数値はすべて整数

入力例 1

3
4 3
2 1
100000 36000

出力例 1

20
1
216261474

1 個目のテストケースについて「富岳 12 景」は次の 12 枚の絵画からなります。

• 地域 1 が描かれた絵画
• 地域 2 が描かれた絵画
• 地域 3 が描かれた絵画
• 地域 4 が描かれた絵画
• 地域 1,2 が描かれた絵画
• 地域 2,3 が描かれた絵画
• 地域 3,4 が描かれた絵画
• 地域 4,1 が描かれた絵画
• 地域 1,2,3 が描かれた絵画
• 地域 2,3,4 が描かれた絵画
• 地域 3,4,1 が描かれた絵画
• 地域 4,1,2 が描かれた絵画

例えば、tatesoto 君が地域 1,2,3,4 の順に訪れたとします。

地域 1 では、

• 地域 1
• 地域 1,2
• 地域 4,1
• 地域 1,2,3
• 地域 3,4,1
• 地域 4,1,2

が描かれた 6 枚の絵画のレプリカを受け取ります。

次に地域 2 では、まだ持っていない

• 地域 2
• 地域 2,3
• 地域 2,3,4

が描かれた 3 枚の絵画のレプリカを受け取ります。

その後、地域 3 では

• 地域 3
• 地域 3,4

が描かれた 2 枚の絵画のレプリカを受け取ります。最後に、地域 4 では地域 4 が描かれた絵画のレプリカを 1 枚受け取ります。

したがって、この訪問順では (C_1,C_2,C_3,C_4)=(6,3,2,1) となります。

地域を訪れる順番を変えることで、異なる列を全部で 20 通り得ることができます。

2 個目のテストケースについて、「富岳 2 景」は次の 2 枚の絵画からなります。

• 地域 1 が描かれた絵画
• 地域 2 が描かれた絵画

どの順番で訪れても各地域で受け取るレプリカは 1 枚なので、得られる列は (1,1) の 1 通りだけです。