Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef lives in an $N \times M$ grid. He is currently participating in a treasure hunt, and has two items left to find. Chef knows that the Manhattan distance between the cells containing these two items is exactly k. He wants to know, in how many different pairs of cells can the two items be present?

Let A_{k} be the number of desired pairs when the value of Manhattan distance between the two cells containing these two items is equal to k. Let $C = \sum_{i=1}^{N + M - 2} A_{i} \cdot 31^{i-1}.$ You have to find the value of C.

The answer may be large, so you need to find it modulo 998244353.

The Manhattan distance between two points (x, y) and (x', y') is defined as |x - x'| + |y - y'|.

------ Input Format ------

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• Each testcase contains of a single line of input, two integers N and M.

------ Output Format ------

On a new line for each test case, print C modulo 998244353

------ Constraints ------

$1 ≤ T ≤ 5$
$1 ≤ N, M ≤ 10^{7}$
- The sum of $N$ over all tests does not exceed $10^{7}$.
- The sum of $M$ over all tests does not exceed $10^{7}$.

------ subtasks ------

Subtask #1 (5 points):
$1 ≤ N, M ≤ 10^{4}$
The sum of $N$ over all tests does not exceed $10^{4}$.
The sum of $M$ over all tests does not exceed $10^{4}$.

Subtask #2 (35 points):
$1 ≤ N, M ≤ 10^{6}$
The sum of $N$ over all tests does not exceed $10^{6}$.
The sum of $M$ over all tests does not exceed $10^{6}$.

Subtask #3 (60 points): original constraints

----- Sample Input 1 ------
3
2 3
2 4
100 350
----- Sample Output 1 ------
2115
65668
895852507
----- explanation 1 ------

Test case $1$:
The pairs of points with distance $1$ are:
- $(1, 1)$ and $(1, 2)$
- $(1, 1)$ and $(2, 1)$
- $(1, 2)$ and $(1, 3)$
- $(1, 2)$ and $(2, 2)$
- $(1, 3)$ and $(2, 3)$
- $(2, 1)$ and $(2, 2)$
- $(2, 2)$ and $(2, 3)$

The pairs of points with distance $2$ are:
- $(1, 1)$ and $(1, 3)$
- $(1, 1)$ and $(2, 2)$
- $(1, 2)$ and $(2, 3)$
- $(1, 2)$ and $(2, 1)$
- $(1, 3)$ and $(2, 2)$
- $(2, 1)$ and $(2, 3)$

The pairs of points with distance $3$ are:
- $(1, 1)$ and $(2, 3)$
- $(2, 1)$ and $(1, 3)$

Therefore, the answer is $7 \cdot 31^{0} + 6 \cdot 31^{1} + 2 \cdot 31^{2}$ = $2115$.

见题面

见题面