Master Pang は、$n \times m$ のチェスボードの左下隅から右上隅まで歩きます。このチェスボードには $n + 1$ 本の水平線分と $m + 1$ 本の垂直線分が含まれています。水平線分は下から上へ $0$ から $n$ まで、垂直線分は左から右へ $0$ から $m$ まで番号が付けられています。水平線分 $r$ と垂直線分 $c$ の交点は $(r, c)$ と表記されます。左下隅は $(0, 0)$ であり、右上隅は $(n, m)$ です。各ステップで、彼は $(x, y)$ から $(x, y + 1)$ へ、または $(x, y)$ から $(x + 1, y)$ へしか移動できません。

$n \times m$ 個の各セルは白または黒に塗られています。頂点 $(i, j), (i+1, j), (i, j+1), (i+1, j+1)$ ($0 \le i < n, 0 \le j < m$) を持つセルは、$i \equiv j \pmod 2$ である場合に限り白く塗られます。

Master Pang の $(0, 0)$ から $(n, m)$ までの歩行経路が与えられたとき、彼のスコアは $a - b$ と定義されます。ここで、$a$ は彼の歩行経路の左側にある白いセルの数、$b$ は彼の歩行経路の左側にある黒いセルの数です。

Master Pang がスコア $k$ となる歩行経路の数を $998244353$ で割った余りを求めてください。

入力

最初の行には単一の整数 $T$ が含まれます（テストケースの数、$1 \le T \le 100$）。 続く $T$ 行の各行には、3つの整数 $n, m, k$ が含まれます（$1 \le n \le 100000, 1 \le m \le 100000, -100000 \le k \le 100000$）。

出力

各テストケースについて、答えを $998244353$ で割った余りを単一の整数で出力してください。

入出力例

入力 1

5
1 1 0
1 1 -1
2 2 1
2 2 0
4 4 1

出力 1

1
0
1
4
16