問題文

PCT 君は $M \times N$ のグリッドで構築される世界の創造神になりました。

以下、上から $i$ 番目、左から $j$ 番目のマスを $(i,j)$ と呼ぶことにします。

この世界に、以下の条件を全て満たすようにいくつかのマスを選び秘宝を埋めることにしました。

• 各マスには秘宝は高々 $1$ 個までしか埋められない。
• 各行の内秘宝は高々 $2$ 個までしか埋められない。
• 秘宝が埋められているマスは隣り合ってはならない。ただし、この世界では $(i,1)$ と $(i,N)$ は隣り合っているものとする。

条件を満たす秘宝の埋め方を $998244353$ で割ったあまりを求めてください。

テストケースは $T$ 個与えられるので、それぞれについて答えを求めてください。

制約

• 入力は全て整数である。
• $1 \le T \le 2 \times 10^5$
• $2 \le N,M \le 2 \times 10^5$
• テストケースの $N$ の総和は $2 \times 10^5$ 以下である。
• テストケースの $M$ の総和は $2 \times 10^5$ 以下である。

入力

入力は以下の形式で与えられます。

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

各ケースは次の形で与えられます。

$N\ M$

出力

$T$ 行出力して最後に改行してください。
$i$ 行目には $i$ 番目のテストケースに対する答えを出力してください。

サンプル

サンプル1

入力

5
4 2
5 6
123 456
1234 5678
3141 5926

出力

35
276561
532350908
204920481
830272369

始めのテストケースに対しては、例えば以下の図 $1$ のような配置が条件を満たします。図 $2$ は $(2,1)$ と $(2,4)$ は両方秘宝が置かれていますが隣り合っているため不適切です。