Master Pang wędruje z lewego dolnego rogu szachownicy o wymiarach $n \times m$ do prawego górnego rogu. Szachownica zawiera $n + 1$ poziomych odcinków linii oraz $m + 1$ pionowych odcinków linii. Poziome odcinki linii są ponumerowane od $0$ do $n$ od dołu do góry, a pionowe od $0$ do $m$ od lewej do prawej. Przecięcie poziomego odcinka linii $r$ oraz pionowego odcinka $c$ oznaczamy jako $(r, c)$. Lewy dolny róg to $(0, 0)$, a prawy górny róg to $(n, m)$. W każdym kroku może on przejść tylko z $(x, y)$ do $(x, y + 1)$ lub z $(x, y)$ do $(x + 1, y)$.

Każda z $n \times m$ komórek jest pokolorowana na biało lub czarno. Komórka o wierzchołkach $(i, j), (i + 1, j), (i, j + 1), (i + 1, j + 1)$ (gdzie $0 \le i < n, 0 \le j < m$) jest pokolorowana na biało wtedy i tylko wtedy, gdy $i \equiv j \pmod 2$.

Dla danej ścieżki Master Panga z $(0, 0)$ do $(n, m)$, jego wynik wynosi $a - b$, gdzie $a$ to liczba białych komórek na lewo od jego ścieżki, a $b$ to liczba czarnych komórek na lewo od jego ścieżki.

Pomóż Master Pangowi obliczyć liczbę ścieżek o wyniku $k$ modulo $998244353$.

Wejście

Pierwsza linia zawiera pojedynczą liczbę całkowitą $T$ — liczbę przypadków testowych ($1 \le T \le 100$). Każda z kolejnych $T$ linii zawiera trzy liczby całkowite $n, m$ oraz $k$ ($1 \le n \le 100000, 1 \le m \le 100000, -100000 \le k \le 100000$).

Wyjście

Dla każdego przypadku testowego wypisz pojedynczą liczbę całkowitą — odpowiedź modulo $998244353$.

Przykład

Wejście 1

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

Wyjście 1

1
0
1
4
16