Non-trivial sequences

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Three integers \(n\), \(m\), and \(k\) are given.

An integer sequence \(a\) is called non-trivial if the following conditions are met.

• The sequence contains \(n\) elements.

• \(0 \le a_i < m\) for all \(1 \le i \le n\).

• \(a_i + a_{i + 1} \not\equiv 0 \pmod k\) for all \(1 \le i \le n - 1\).

Count the number of non-trivial sequences. Since this number can be very large, output the remainder of its division by the prime number \(988244353\).

Input

The first line contains a single integer \(t\) — the number of test cases.

Each of the next \(t\) lines contains three integers \(n\), \(m\), and \(k\).

Output

In \(t\) lines, output one integer each — the remainder of the number of non-trivial sequences divided by \(988244353\).

Constraints

\(1 \le t \le 10^4\),

\(1 \le n, m, k \le 10^{18}\).

Samples