H. Hilly Array
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

An array $$$h$$$ of length $$$l$$$ is a hilly array if $$$h_i = \min(i, \, l - i + 1)$$$ for every $$$1 \le i \le l$$$. That is, it rises $$$1, 2, 3, \ldots$$$ up to a peak of $$$\left\lceil l/2 \right\rceil$$$ in the middle and then mirrors back down. For example, the hilly array of length $$$5$$$ is $$$[1, 2, 3, 2, 1]$$$ and the one of length $$$6$$$ is $$$[1, 2, 3, 3, 2, 1]$$$. Each length gives exactly one hilly array.

Consider $$$n$$$ intervals, where the $$$i$$$-th interval is $$$[a_i, b_i]$$$. An interval contains a value $$$v$$$ if $$$a_i \le v \le b_i$$$; if $$$a_i \gt b_i$$$, the interval is empty and contains nothing.

A hilly array of length $$$x$$$ fits a sequence of intervals if we can find a subsequence of $$$x$$$ intervals such that each element of the hilly array, in order, comes from the corresponding interval in the subsequence. Formally, a hilly array $$$h$$$ of length $$$x$$$ fits a sequence of $$$n$$$ intervals if there are positions $$$1 \le i_1 \lt i_2 \lt \cdots \lt i_x \le n$$$ such that interval $$$i_j$$$ contains $$$h_j$$$ for every $$$1 \le j \le x$$$. Let $$$f$$$ be the length of the longest hilly array that fits, or $$$0$$$ if none does.

For example, take the $$$5$$$ intervals $$$[1,1], [2,1], [2,2], [1,1], [1,2]$$$. The longest hilly array that fits is $$$[1,2,1]$$$, placed at intervals $$$1$$$, $$$3$$$, and $$$5$$$, which contain $$$1$$$, $$$2$$$, and $$$1$$$ respectively. So $$$f = 3$$$ here.

You are given two integers $$$n$$$ and $$$k$$$. Compute the sum of $$$f$$$ over all $$$k^{2n}$$$ ways to form the sequence of intervals, where each $$$a_i$$$ and each $$$b_i$$$ independently takes a value from $$$1$$$ to $$$k$$$. Since the answer can be large, output it modulo $$$998244353$$$.

Input

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

The first and only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n, k \leq 5000$$$) — the number of intervals and the largest value each $$$a_i$$$ and $$$b_i$$$ can take.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$, and the sum of $$$k$$$ over all test cases does not exceed $$$5000$$$.

Output

For each test case, print a single integer — the required sum modulo $$$998244353$$$.

Example
Input
3
2 2
3 3
2 1
Output
16
738
2
Note

In the first test case $$$n = 2$$$ and $$$k = 2$$$, so each interval is one of $$$[1,1]$$$, $$$[1,2]$$$, $$$[2,1]$$$, $$$[2,2]$$$ (note $$$[2,1]$$$ is empty), giving $$$16$$$ ways to choose the two intervals. The value of $$$f$$$ for each way, with the first interval as the row and the second as the column, is:

$$$[1,1]$$$$$$[1,2]$$$$$$[2,1]$$$$$$[2,2]$$$
$$$[1,1]$$$$$$2$$$$$$2$$$$$$1$$$$$$1$$$
$$$[1,2]$$$$$$2$$$$$$2$$$$$$1$$$$$$1$$$
$$$[2,1]$$$$$$1$$$$$$1$$$$$$0$$$$$$0$$$
$$$[2,2]$$$$$$1$$$$$$1$$$$$$0$$$$$$0$$$

For instance:

  • Both intervals $$$[1,1]$$$: the length-$$$2$$$ hilly array $$$[1,1]$$$ fits, with a $$$1$$$ placed in each interval, so $$$f = 2$$$.
  • First interval $$$[1,2]$$$, second $$$[2,2]$$$: only the first interval contains $$$1$$$, so $$$[1]$$$ fits but $$$[1,1]$$$ does not, and $$$f = 1$$$.
  • Both intervals $$$[2,1]$$$: both are empty, so no value can be placed anywhere and $$$f = 0$$$.

Summing the values in the table gives $$$2 \cdot 4 + 1 \cdot 8 + 0 \cdot 4 = 16$$$.