Problem Statement

Rooms are arranged in a grid with $H$ rows and $W$ columns. There are walls between adjacent rooms that share an edge. When you are in room $A$ and room $B$ is adjacent to room $A$ in one of the four directions (up, down, left, right), and the wall between room $A$ and room $B$ has been demolished, you can move from room $A$ to room $B$.

Find the total number, modulo $998244353$, of ways to choose $K$ walls such that the following condition is satisfied.

• When all chosen walls are demolished, it is possible to move from the top-left room to the bottom-right room by passing through some rooms.

Solve $T$ test cases for each input file.

Constraints

• $1 \leq T \leq 2 \times 10^5$
• $2 \leq H \leq 2 \times 10^5$
• $2 \leq W \leq 2 \times 10^5$
• $\boldsymbol{0 \leq K \leq H+W}$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each case is given in the following format:

H W K

Output

Output the answers in a total of $T$ lines. The $t$-th line should contain the total number, modulo $998244353$, of ways to select $K$ walls that satisfy the condition for the $t$-th test case.