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$ 个测试用例的答案。

样例解释 1

对于第一个测试用例，比如字符串 ACBC 满足条件。ACBC 本身包含了 ABC 作为子序列，而 ACC 不包含 ABC 作为子序列，因此最大不包含 ABC 作为子序列的子序列长度为 $3$。其它满足的例子有 AABC、ABCA 等。

约束条件

• $1 \le T \le 2 \times 10^5$
• $1 \le N \le 10^6$
• $\max(0, N-100) \le K \le N$

由 ChatGPT 5 翻译