We have two generators made by AI. One is wrong on one test, the other is wrong on another - 马德尤

Task

The organizing committee decided to be very short, brief and terse with the statement of this problem, because of many obvious reasons.

We call an array of integer elements chic if the sum of its elements is even.

Consider $\nabla(N, M)$ = the number of arrays of $N$ elements from $\{0, 1, \ldots, M\}$ such that the chosen array has an even number of chic subarrays.

Given $N$ and $M$, compute

Input data

You will have to answer $T$ tests. On the next $T$ lines, you will be given two numbers, $N$ and $M$, with their meaning explained above.

Output data

You will have to print $T$ integers $-$ the answer for each case.

Constraints and clarifications

• $1 \leq T \leq 4$
• $1 \leq N \leq 10^5$, for all tests;
• $1 \leq M \leq 10^9$, for all tests;
• A subarray of an array $V$ with $N$ elements is any contiguous subsequence of it (that is, of the form $V_l,V_{l+1},\ldots, V_r$ for some $l$ and $r$ with $0 \leq l \leq r < N$).

Example

stdin

2
1 3
2 3

stdout

4
0

Explanation

There are $T = 2$ cases.

For the first case, one can compute that $\nabla(1, 0) = 0, \nabla(1, 1) = 1,\nabla(1,2) = 1$ and $\nabla(1, 3) = 2$. Thus, the sum is $(0+1+1+2) \bmod 998244353 = 4$.

For the second case, it can be proven that there exist no arrays that satisfy the \textit{chic} condition.