e4e5 Ke2? Ke7?

Description

Solve the problem below for \(T\) test cases.

You have a chess board of dimension \(1 \times M\) with positions numbered from \(1\) to \(M\) from left to right. You have \(N\) identical pawns, initially lined up from position \(1\) to \(N\) on the chess board. You can do any of the following operations as many number of times in any order:

• Select the \(i\)-th pawn from the left (\(1 \le i \le N - 2\)) such that the right of the \((i + 2)\)-th pawn is inside the chessboard, and move the \(i\)-th pawn one position to the right of the \((i+2)\)-th pawn. While there are two pawns on the same position, move one of the pawns one position to the left.
• Rotate the board \(180\) degrees, i.e., a pawn at position \(x\) will end up at position \(M - x + 1\).

Find the number of distinct configurations of pawns that you can end up with after doing the above operations modulo \(998244353\).

Two configurations are considered distinct if there is at least one position where one configuration has a pawn but not the other.

Constraints

• \(1 \le T \le 10000\)
• \(3 \le N \le M \le 200\;000\)

Input

The first line contains the number of test cases is in the following format:

T

Then \(T\) test cases follow, each in the following format:

N M

Output

For each test case, output an integer representing the number of distinct configurations modulo \(998244353\).

Sample Input

2
4 6
69 420

Sample Output

11
440614405

Explanation

By letting \(\texttt{1}\) denote pawns and \(\texttt{0}\) denote empty positions, the possible configurations for the first example are:

• \(\texttt{111100}\)
• \(\texttt{111010}\)
• \(\texttt{111001}\)
• \(\texttt{110101}\)
• \(\texttt{101110}\)
• \(\texttt{101011}\)
• \(\texttt{100111}\)
• \(\texttt{011110}\)
• \(\texttt{011101}\)
• \(\texttt{010111}\)
• \(\texttt{001111}\)