Problem Statement

How many ways are there to color a grid with $H$ rows and $W$ columns, connected in the shape of a torus, in black and white so that the following conditions are satisfied?

• There are exactly $1$ black connected components.
• The black connected component has both width and height exactly $3$ at every location.

Find the answer mod $998244353$.

For $1$ input, answer $T$ test cases.

Formal Problem Statement

There is a grid with $H$ rows and $W$ columns. The cell in row $i\ (0 \leq i \lt H)$ and column $j\ (0 \leq j \lt W)$ is called cell $(i,j)$. Cell $(i,j)$ is adjacent to cell $((i+1)\bmod H,\,j)$, cell $((i-1)\bmod H,\,j)$, cell $(i,\,(j+1)\bmod W)$, and cell $(i,\,(j-1)\bmod W)$.

Find the number, modulo $998244353$, of ways to color the cells in black and white so that the following conditions are satisfied.

• $1$ or more cells are painted black.
• For any pair of black cells $a,b$, it is possible to reach $b$ from $a$ by moving through adjacent black cells.
• For any black cell, the number of cells reachable by moving through adjacent black cells in the same row $0$ or more times is exactly $3$.
• For any black cell, the number of cells reachable by moving through adjacent black cells in the same column $0$ or more times is exactly $3$.

For $1$ input, answer $T$ test cases.

Constraints

• $1 \leq T \leq 256$
• $4 \leq H,W \leq 10^5$

Input

First, line $1$ contains the number of test cases $T$ in the input.

$T$

Then, $T$ test cases are given over $T$ lines. Each test case is given on $1$ line in the following format.

$H\ W$

Output

Print $T$ lines. On line $i$ $(1 \leq i \leq T)$, print the answer to the $i$-th test case.

Sample

3
4 4
4 5
100000 100000

40
20
604213015