AT_bogosortcontest_div1_a Fugaku NK-kei

富士山の周囲には、 $ 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 $ 個のテストケースについて答えてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ K $

各テストケースについて、答えを出力せよ。

### Sample Explanation 1 $ 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 $ 通りだけです。 ### Constraints - $ 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 $ 以下 - 入力される数値はすべて整数