Given $n$ and $m$.

Find the number of distinct sequences of positive integers $a_1, a_2, \dots, a_n$ such that for all $1 \leq i \leq n$, $1 \leq a_i \leq m$, and there exist no $1 \leq i < j \leq n$ satisfying $\max\limits_{k=1}^i a_k = \min\limits_{k=j}^n a_k$. Output the answer modulo $998244353$.

Input

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

Each of the following $T$ lines contains two positive integers $n$ and $m$.

Output

For each test case, output a single integer on a new line representing the answer modulo $998244353$.

Subtasks

For $50\%$ of the data, $n \leq 50$.

For $100\%$ of the data, $1 \leq T \leq 10^5$, $1 \leq n \leq 300$, $1 \leq m \leq 10^9$.

Examples

Input 1

3
3 2
3 3
4 10

Output 1

2
12
7500