問題文

トーラス状に繋がった $H$ 行 $W$ 列のマス目を白黒で塗り分ける方法であって以下の条件を満たすものは何通りあるでしょう？

• 黒の連結成分はちょうど $1$ 個
• 黒の連結成分は全ての場所で幅・高さ共にちょうど $3$

答えは mod $998244353$ で求めてください。

$1$ つの入力につき、$T$ 個のテストケースに答えてください。

厳密な問題文

$H$ 行 $W$ 列のマス目がある。 $i\ (0 \leq i \lt H)$ 行目 $j\ (0 \leq j \lt W)$ 列目のマスをマス $(i,j)$ と呼ぶ。 マス $(i,j)$ はマス $((i+1)\bmod H,\,j)$、マス $((i-1)\bmod H,\,j)$、マス $(i,\,(j+1)\bmod W)$、マス $(i,\,(j-1)\bmod W)$ に隣接している。

以下の条件を満たすようにマスを白黒で塗り分ける場合の数を $998244353$ で割った余りを求めよ。

• $1$ つ以上のマスを黒く塗る。
• 任意の黒マスの組 $a,b$ について、隣接する黒マスを辿ることにより $a$ から $b$ まで到達することができる。
• 任意の黒マスについて、同じ行の隣接する黒マスを $0$ 回以上辿ることによって到達できるマスの個数がちょうど $3$。
• 任意の黒マスについて、同じ列の隣接する黒マスを $0$ 回以上辿ることによって到達できるマスの個数がちょうど $3$。

$1$ つの入力につき、$T$ 個のテストケースに答えよ。

制約

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

入力

まず $1$ 行目に、入力に含まれるテストケースの数 $T$ が与えられます。

$T$

その後、$T$ 行にわたって $T$ 個のテストケースが与えられます。各テストケースは次の形式で $1$ 行で与えられます。

$H\ W$

出力

$T$ 行出力してください。 $i$ 行目 $(1 \leq i \leq T)$ には、$i$ 番目のテストケースに対する回答を出力してください。

サンプル

3
4 4
4 5
100000 100000

40
20
604213015