Даны $n$ и $m$.

Найдите количество различных последовательностей положительных целых чисел $a_1, a_2, \dots, a_n$ таких, что для любого $1 \leq i \leq n$ выполняется $1 \leq a_i \leq m$, и не существует пары индексов $1 \leq i < j \leq n$, для которой $\max\limits_{k=1}^i a_k = \min\limits_{k=j}^n a_k$. Ответ выведите по модулю $998244353$.

Входные данные

Первая строка содержит целое число $T$ — количество тестовых случаев.

Далее следуют $T$ строк, каждая из которых содержит два целых числа $n$ и $m$.

Выходные данные

Для каждого теста выведите в отдельной строке количество таких последовательностей по модулю $998244353$.

Примеры

Пример 1

3
3 2
3 3
4 10

Выходные данные 1

2
12
7500

Подзадачи

Для $50\%$ данных гарантируется, что $n \leq 50$.

Для $100\%$ данных гарантируется, что $1 \leq T \leq 10^5$, $1 \leq n \leq 300$, $1 \leq m \leq 10^9$.