Небанальні послідовності

Limits: 2 sec., 256 MiB

Задано три цілі числа \(n\), \(m\) та \(k\).

Цілочислова послідовність \(a\) називається небанальною, якщо виконуються такі умови.

• Послідовність містить \(n\) елементів.

• \(0 \le a_i < m\) для всіх \(1 \le i \le n\).

• \(a_i + a_{i + 1} \not\equiv 0 \pmod k\) для всіх \(1 \le i \le n - 1\).

Порахуйте кількість небанальних послідовностей. Оскільки це число може бути дуже великим, виведіть остачу від його ділення на просте число \(988244353\).

Input

В першому рядку задано одне ціле число \(t\) — кількість тестів.

В кожному з \(t\) наступних рядків задано по три цілі числа \(n\), \(m\) та \(k\).

Output

В \(t\) рядках виведіть по одному цілому числу — остачу від ділення кількості небанальних послідовностей на \(988244353\).

Constraints

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

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

Samples