G. A Counting Problem
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Note: You may want to use $$$64$$$-bit integers instead of $$$32$$$-bit integers in this task. For example, in Java, you may want to use long instead of int. In C++, you may want to use long long.

Given an array $$$a$$$ of size $$$m$$$, let $$$f(a)$$$ be the number of numbers $$$1\leq i\leq m$$$ where $$$\min(a_1,a_2,\ldots,a_i)=a_i$$$.

For example, if $$$a=[2,4,3,2,1]$$$, $$$f(a)=3$$$ because $$$a_1=\min(a_1)$$$, $$$a_4=\min(a_1,a_2,a_3,a_4)$$$, and $$$a_5=\min(a_1,a_2,a_3,a_4,a_5)$$$.

Seele gives you two integers $$$n$$$ and $$$k$$$.

There are $$$k^n$$$ length-$$$n$$$ arrays such that each element is a positive integer from $$$1$$$ to $$$k$$$, inclusive. Over all such arrays, Seele asks you to output the sum of $$$f(a)$$$ over all such arrays $$$a$$$.

Since the answer may be huge, output the answer modulo $$$998\,244\,353$$$.

Input

The first test case contains an integer $$$t$$$ – the number of independent test cases ($$$1 \leq t \leq 10^4$$$).

The only line of each test case contains two integers $$$n,k$$$ ($$$1 \leq n \leq 10^9, 1 \leq k \leq 3\cdot 10^5$$$).

It is guaranteed that the sum of $$$k$$$ does not exceed $$$3\cdot 10^5$$$ over all test cases.

Scoring

Partial credits will be given to programs who pass tests with smaller constraints outlined below.

GroupPointsConstraints
110$$$n\leq 7$$$, the sum of $$$k^n$$$ does not exceed $$$1.5\cdot 10^5$$$ over all test cases.
215$$$k=2$$$, sum of $$$n$$$ does not exceed $$$3000$$$ over all test cases.
320$$$k=2$$$, sum of $$$n$$$ does not exceed $$$3\cdot 10^5$$$ over all test cases.
425The sum of $$$n\cdot k$$$ does not exceed $$$10^6$$$ over all test cases.
530No further constraints
Output

For each test case, output the answer modulo $$$998\,244\,353$$$.

Examples
Input
5
2 2
3 2
3 3
5 5
888 999
Output
7
19
59
8479
667852386
Input
1
1000000000 300000
Output
732088305
Note

The first examples satisfies subtask $$$4$$$ and the second example satisfies subtask $$$5$$$.

In the first test case of the first example, we need to consider the following four arrays:

  • $$$f([1,1])=2$$$.
  • $$$f([1,2])=1$$$.
  • $$$f([2,1])=2$$$.
  • $$$f([2,2])=2$$$.

The sum over all arrays is $$$7$$$.