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