405966: GYM102192 F Boolean 3-Array

F. Boolean 3-Arraytime limit per test2 secondsmemory limit per test128 megabytesinputstandard inputoutputstandard output

In this problem, we are going to deal with a special structure called Boolean 3-array.

A Boolean 3-array of size m × n × p is a three-dimensional array denoted as A, where (1 ≤ i ≤ m, 1 ≤ j ≤ n, 1 ≤ k ≤ p). We define any one of these as an operation on a Boolean 3-array A of size m × n × p:

• Choose some fixed a (1 ≤ a ≤ m), then flip A[a][j][k] for all 1 ≤ j ≤ n, 1 ≤ k ≤ p;
• Choose some fixed b (1 ≤ b ≤ n), then flip A[i][b][k] for all 1 ≤ i ≤ m, 1 ≤ k ≤ p;
• Choose some fixed c (1 ≤ c ≤ p), then flip A[i][j][c] for all 1 ≤ i ≤ m, 1 ≤ j ≤ n;
• Choose some fixed a₁, a₂ (1 ≤ a₁, a₂ ≤ m), then swap A[a₁][j][k] and A[a₂][j][k] for all 1 ≤ j ≤ n, 1 ≤ k ≤ p;
• Choose some fixed b₁, b₂ (1 ≤ b₁, b₂ ≤ n), then swap A[i][b₁][k] and A[i][b₂][k] for all 1 ≤ i ≤ m, 1 ≤ k ≤ p;
• Choose some fixed c₁, c₂ (1 ≤ c₁, c₂ ≤ p), then swap A[i][j][c₁] and A[i][j][c₂] for all 1 ≤ i ≤ m, 1 ≤ j ≤ n.

Here "filp" means change the value of the element, i.e., replace 0 with 1 and replace 1 with 0.

We say two Boolean 3-arrays A, B are essentially identical, if and only if any one of them can be transformed to the other, by applying operations finitely many times; otherwise, we say A and B are essentially different.

Now, given the size of the Boolean 3-array, can you determine the maximum number of Boolean 3-arrays of given size you may choose, such that any two of them are essentially different?

Input

The first line of input is a single integer T (1 ≤ T ≤ 300), the number of test cases.

Each test case is a single line of three integers n, m, p (1 ≤ m, n, p ≤ 13), the size of the Boolean 3-array.

Output

For each test case, display an integer in a single line: the answer modulo 998244353.

ExampleInput

3
1 1 1
2 2 2
2 3 4

Output

1
9
723