Problem Statement

315-san is studying magic circles.
Magic circles come in various shapes, such as pentagrams, hexagrams, and circular formations, and they take effect when catalysts of appropriate strength are placed on them.
The magic circle to be drawn this time is a rectangle divided into $H$ parts vertically and $W$ parts horizontally, and it takes effect by placing catalysts on its cells.
However, if a magic circle does not maintain harmony, the propagation of magical power becomes uneven, and the spell eventually breaks down.
The magic circle drawn this time is said to maintain harmony when, for every cell, the sum $S$ of the strengths of the catalysts in the $3 \times 3$ cell range centered on that cell is the same.
That is, letting $M_{y, x}$ be the strength of the catalyst in cell $(x, y)$, it must hold that $\sum_{i=y-1}^{y+1} \sum_{j=x-1}^{x+1} M_{i, j} = S$ for all integers $x, y$ satisfying $1 \leq x \leq W, 1 \leq y \leq H$.
In this case, the strength of the magic circle is $S$.
315-san has many catalysts of strengths between $1$ and $9$, inclusive, and wants to create a magic circle of strength $X$ that maintains harmony by placing these catalysts appropriately.
At most 1 catalyst can be placed on each cell (it is also possible to place none), so $0 \leq M_{y, x} \leq 9$ for all integers $x, y$ satisfying $1 \leq x \leq W, 1 \leq y \leq H$, and $M_{y, x} = 0$ for all other $x, y$.
There are $10^{WH}$ ways in total to place catalysts on the magic circle; among them, what placements make the magic circle maintain harmony?
There are $T$ test cases in total.
For each test case, $W_i, H_i, X_i$ are given; find the number of magic circles of strength $X_i$ that maintain harmony.
Since the answer can be very large, output the answer modulo $998244353$ (a prime).

Input

$T$
$W_1\ H_1\ X_1$
$\vdots$
$W_T\ H_T\ X_T$

• $1 \leq T \leq 10000$
• $1 \leq W_i, H_i \leq 600$
• $0 \leq X_i \leq 81$
• All inputs are integers

Output

On line $i$, find the number of magic circles that maintain harmony with height $H_i$, width $W_i$, and strength $X_i$, and output the answer modulo $998244353(= 119 \times 2^{23} + 1)$.
Print a newline at the end.

Sample

1
2 2 6

84

1
5 2 4

259

1
3 3 81

0