Background

I often reminisce about the past...

Three years ago, little Glycogen was a cute seventh-grade girl, and she was classmates with Yuting-chan...

Description

Let's get back to the topic. In a seventh-grade math study group, little Glycogen once solved the following problem:

Prove that for any sequence $a_0, a_1, a_2, a_3$ of length $4$ consisting only of $\pm 1$, $4 \mid a_0a_1 + a_1a_2 + a_2a_3 + a_3a_0$.

The cute little Glycogen solved this problem instantly, which made her very happy. Three years later, having developed a $\overset{\text{counting}}{\text{bad habit}}$, she wants to strengthen this problem. 🥰

For a sequence $a_0 \dots a_{n-1}$ of length $n$ consisting only of $\pm 1$, we define its rain function as: $$ S(a, m) = \displaystyle \sum_{k = 0}^{n - 1} \prod_{l = 0}^{m - 1} a_{(k + l) \bmod n} $$ Given $n, m, k$, find how many of the $2^n$ different sequences $a$ satisfy $S(a, m) = k$. Output the count modulo $998,244,353$.

Input

This problem contains multiple test cases.

The first line contains a positive integer $T$, representing the number of test cases.

The next $T$ lines each contain three integers $n, m, k$.

Output

Output $T$ lines, each containing an integer representing the answer for one test case.

Examples

Input 1

9
4 2 0
9 9 -9
9 3 3
20 8 -12
114 5 14
191 9 81
1036 854 104
998244 353 4
2147483 64 7

Output 1

12
256
108
10000
661235724
741150826
500003636
222931421
404094315

Note 1

For the first test case of the first example, the sequences that do not satisfy the condition are $a=[1,1,1,1]$, $a=[-1,-1,-1,-1]$, $a=[1,-1,1,-1]$, and $a=[-1,1,-1,1]$, so the answer is $2^4-4=12$.

For the second test case of the first example, the sequences that satisfy the condition are those with an odd number of $-1$s, so the answer is $2^8=256$.

Input 2

6
8 4 0
12 4 0
16 4 0
20 4 0
24 4 0
28 4 0

Output 2

176
1728
26160
368000
5413856
80212608

Input 3

4
6 2 0
10 2 0
9 9 7
9 3 6

Output 3

0
0
0
0

Subtasks

This problem uses bundled testing.

For all data, it is guaranteed that $2 \leq m \leq n \leq 5\times 10^6$, $0 \leq \lvert k\rvert \leq n$, $1 \leq T \leq 10$, and $\sum n \leq 5\times 10^6$.