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