Problem Statement

There is a grid with $H$ rows and $W$ columns.

This grid has $H(W+1)$ vertical edges and $W(H+1)$ horizontal edges, for a total of $H(W+1) + W(H+1)$ (see also the figures at Sample Input/Output). Consider marking these edges by the following two kinds of operations.

• Operation (1): Choose a square whose left and upper edges are unmarked when performing this operation. Mark the left and upper edges of that square.
• Operation (2): Choose a square whose right and lower edges are unmarked when performing this operation. Mark the right and lower edges of that square.

Find the number, modulo $998244353$, of possible sets of edges that are eventually marked when Operations (1) and (2) can be performed any number of times, possibly zero.

You have $T$ test cases to solve.

Constraints

• $1\leq T\leq 2\times 10^5$
• $1\leq H, W\leq 10^6$

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\vdots
\text{case}_T

Each test case is given in the following format:

H W

Output

Print $T$ lines. The $i$-th line should contain the number, modulo $998244353$, of possible sets of edges that are eventually marked for the $i$-th test case.