Background

Looking back to the past, the sky was clear, the sun was warm, and the breeze was gentle.
Creek stones, with different depths and heights, were scattered in the crystal-clear Mengfeng Creek like jade.
The endless fun memories of raccoons doing parkour on the water also began here...

Problem Description

As the sun rises and the moon sets, spring goes and autumn comes, the heights of the Mengfeng creek stones change in countless ways.
The thoughtful little raccoon CleverRaccoon wants to find out how many different height sequences these creek stones can form.

Now there are some non-negative integer sequences $a$ of length $n$.

When $n>1$, $a_1,a_n$ take values in $0\sim m$, and the other elements $a_i$ take values in $0\sim m-1$, where $2\leq i \leq n-1$.

When $n=1$, $a_1$ takes values in $0\sim m+1$.

Definition: Sequences $a,b$ are considered the same if and only if either $\forall i\in\{1,2,\dots ,n\},a_i=b_i$ or $\forall i\in\{1,2,\dots ,n\},a_i=b_{n-i+1}$.

Given $n,m$, find the maximum number of different sequences. Output the answer modulo $998244353$.

Input Format

This problem contains multiple test cases.

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

The next $T$ lines each contain two positive integers $n,m$ separated by spaces, with meanings as described above.

Output Format

Output $T$ lines. For each test case, output one positive integer, the answer modulo $998244353$.

3
1 3
2 2
6 3

5
6
666

Hint

Explanation #1

When $n=1,m=3$, $a_i\in\{0,1,2,3,4\}$, so there are $5$ different height sequences in total.

When $n=2,m=2$, there are $6$ different height sequences in total, listed as follows:

Constraints

This problem uses bundled Subtasks.

For $100\%$ of the testdata, it is guaranteed that $1\leq n\leq10^{18},1\leq m\leq10^9,1\leq T\leq10^6$.

Translated by ChatGPT 5