King of Rats

Nous vivrons. Et nous guérirons. Les cicatrices... Nous les gardons. Pour ne pas oublier.

After an overwhelming battle against the rats, it is time for Amicia and Hugo to flee from the army of Count Victor de Arles. The soldiers have positioned themselves on a narrow path, which can be represented as a matrix of dimensions $2 \cdot n$. Furthermore, we know that there are a total of $k$ soldiers on this path.

Task

Amicia and Hugo define the danger of a configuration as the number of soldier groups in it. More formally, if we consider a $2 \times n$ binary matrix, where we have $1$ in the positions where a soldier exists. We say that two cells are connected if they both have value $1$ and they share an edge. Note that this relation is transitive, meaning that if two cells $a$ and $b$ are connected and cells $b$ and $c$ are connected, than $a$ and $c$ are also considered connected. A connected component is a maximal subset of connected cells with value $1$. The danger is the number of connected components in this matrix.

Your task is to help the two protagonists find the expected value of the danger, considering all possible configurations. Each configuration is considered equiprobable. In this case, the expected value can be defined as the average number of connected components across all possible configurations.

Implementation

You have to implement the following functions:

void prec(int subtask_id)
int solve(int n, int k)

The first function will be called once at the beginning of the grader. You can use it for preprocessing.

The second function should return the expected danger, given the $n$ and $k$ parameters, modulo $998 \ 244 \ 353$. Formally, let $M = 998 \ 244 \ 353$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not\equiv 0 \pmod{M}$. Return the integer equal to $p \cdot q^{-1} \pmod{M}$. In other words, return such an integer $x$ that $0 \leq x < M$ and $x \cdot q \equiv p \pmod{M}$.

The second function will be called $t$ times. This means there are multiple testcases in the input!

Do not forget to include the header file "kor.h", otherwise you will get compile error!

Constraints

• $1 \leq t \leq 10$
• $1 \leq n \leq 10^9$
• $0 \leq k \leq 10^6$
• $k \leq 2 \cdot n$

Example 1

input

2
6
2 2
5 10
2000 3
2000 5
100 32
150 278

output

332748119
1
518205646
742082393
368118258
937239298

Explanation

Note that the grader should be provided with the subtask of the test, the number of testcases $t$ and the values $n, k$ for each testcase.

For the first testcase of the first sample, the possible configurations are shown below:

There is a total of $6$ configurations, $4$ of which have a single component. The answer is thus $\frac{4 \cdot 1 + 2 \cdot 2}{6} = \frac{4}{3}$

Example 2

input

7
8
100000000 0
100000000 1
100000000 2
100000000 3
5219873 192
853875838 238
43782384 1500
58123292 180000

output

0
1
268791198
806373591
782159797
435727907
712321002
257644694