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$ 行，每行包含三個整數 $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