AT_arc209_e [ARC209E] I hate ABC

長さ $ N $ の `A`, `B`, `C` からなる文字列 $ S $ のうち、以下の値が $ K $ になるものの個数を $ 998244353 $ で割った余りを求めてください。 - $ S $ の(連続とは限らない)部分列のうち、(連続とは限らない)部分列として `ABC` を含まないものの長さの最大値 $ T $ 個のテストケースが与えられるので、それぞれについて解いてください。

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

$ T $ 行出力せよ。 $ i(1 \le i \le T) $ 行目には、 $ i $ 番目のテストケースの答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて、例えば `ACBC` は条件を満たします。`ACBC` 自身は部分列に `ABC` を含み、`ACC` は部分列に `ABC` を含まないため、部分列に `ABC` を含まないような部分列の長さの最大値は $ 3 $ となります。 他にも `AABC`, `ABCA` などが条件を満たします。 ### Constraints - $ 1 \le T \le 2 \times 10^5 $ - $ 1 \le N \le 10^6 $ - $ \max(0,N-100) \le K \le N $