Problem Description

You are given three positive integers $n$, $m$, and $k$.

Your task is to calculate the total number of sequences $A$ of length $n$ that satisfy the following conditions:

1. All elements of $A$ are integers from $1$ to $m$（inclusive）.

2. Let $A_i$ be the $i$-th element of sequence $A$. For all positive integers $i$ not exceeding $k$, it is satisfied that $A_i = A_{n-k+i}$.

Calculate the total number of such sequences $A$ that satisfy the conditions and output the result modulo 998244353.

Input

The first line contains an integer $T （T\leq 1000）$, representing the number of test cases.

Each of the next $T$ lines contains three integers $n$, $m$, and $k（1 \leq n,m,k \leq 10^{18} , k \leq n）$, representing the parameters for one test case.

Output

For each test case, output an integer representing the answer.

1
11 2 1

1024