E - I hate ABC 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MiB

配点 : 1100 点

問題文

長さ N の A, B, C からなる文字列 S のうち、以下の値が K になるものの個数を 998244353 で割った余りを求めてください。

  • S の(連続とは限らない)部分列のうち、(連続とは限らない)部分列として ABC を含まないものの長さの最大値

T 個のテストケースが与えられるので、それぞれについて解いてください。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各ケースは以下の形式で与えられる。

N\ K

出力

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

入力例 1

4
4 3
8 6
123 100
123456 123400

出力例 1

9
462
741573397
255048895

1 番目のテストケースについて、例えば ACBC は条件を満たします。ACBC 自身は部分列に ABC を含み、ACC は部分列に ABC を含まないため、部分列に ABC を含まないような部分列の長さの最大値は 3 となります。 他にも AABC, ABCA などが条件を満たします。

Score : 1100 points

Problem Statement

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.

Constraints

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

Input

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

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

Sample Input 1

4
4 3
8 6
123 100
123456 123400

Sample Output 1

9
462
741573397
255048895

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.