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.