AT_arc209_e [ARC209E] I hate ABC

Find the number, modulo $ 998244353 $ , of strings $ S $ of length $ N $ consisting of `A`, `B`, `C` such that the following value equals $ K $ : - The maximum length of a (not necessarily contiguous) subsequence of $ S $ that does not contain `ABC` as a (not necessarily contiguous) subsequence You are given $ T $ test cases. Solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each case is given in the following format: > $ N\ K $

Output $ T $ lines. The $ i $ -th line $ (1 \le i \le T) $ should contain the answer to the $ i $ -th test case.

### Sample Explanation 1 For the first test case, for example, `ACBC` satisfies the condition. `ACBC` itself contains `ABC` as a subsequence, and `ACC` does not contain `ABC` as a subsequence, so the maximum length of a subsequence that does not contain `ABC` as a subsequence is $ 3 $ . Other examples that satisfy the condition include `AABC` and `ABCA`. ### Constraints - $ 1 \le T \le 2 \times 10^5 $ - $ 1 \le N \le 10^6 $ - $ \max(0,N-100) \le K \le N $