{"raw_statement":[{"iden":"problem statement","content":"Find the number, modulo $998244353$, of strings $S$ of length $N$ consisting of `A`, `B`, `C` such that the following value equals $K$:\n\n*   The maximum length of a (not necessarily contiguous) subsequence of $S$ that does not contain `ABC` as a (not necessarily contiguous) subsequence\n\nYou are given $T$ test cases. Solve each of them."},{"iden":"constraints","content":"*   $1 \\le T \\le 2 \\times 10^5$\n*   $1 \\le N \\le 10^6$\n*   $\\max(0,N-100) \\le K \\le N$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach case is given in the following format:\n\n$N\\ K$"},{"iden":"sample input 1","content":"4\n4 3\n8 6\n123 100\n123456 123400"},{"iden":"sample output 1","content":"9\n462\n741573397\n255048895\n\nFor 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`."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}