Problem Statement

PCT has become the creator god of a world built on an $M \times N$ grid.

Below, the cell in the $i$-th row from the top and the $j$-th column from the left is called $(i,j)$.

He has decided to choose some cells in this world and bury treasures in them so that all of the following conditions are satisfied.

• At most $1$ treasure can be buried in each cell.
• At most $2$ treasures can be buried in each row.
• Cells in which treasures are buried must not be adjacent to each other. Here, in this world, $(i,1)$ and $(i,N)$ are considered adjacent.

Find the number of ways to bury the treasures satisfying the conditions, modulo $998244353$.

$T$ test cases are given; find the answer for each of them.

Constraints

• All inputs are integers.
• $1 \le T \le 2 \times 10^5$
• $2 \le N,M \le 2 \times 10^5$
• The sum of $N$ over the test cases is at most $2 \times 10^5$.
• The sum of $M$ over the test cases is at most $2 \times 10^5$.

Input

The input is given in the following format.

$T$
$\mathrm{case}1$
$\vdots$
$\mathrm{case}T$

Each case is given in the following format.

$N\ M$

Output

Output $T$ lines, followed by a newline at the end.
On the $i$-th line, output the answer for the $i$-th test case.

Sample

Sample 1

Input

5
4 2
5 6
123 456
1234 5678
3141 5926

Output

35
276561
532350908
204920481
830272369

For the first test case, for example, an arrangement like Figure $1$ below satisfies the conditions. In Figure $2$, treasures are placed on both $(2,1)$ and $(2,4)$, but it is invalid because they are adjacent.