Problem Statement

You are given positive integers $N,M$.

Find the number, modulo $998244353$, of non-negative integer sequences $A=(A_1,A_2,\ldots,A_N)$ of length $N$ that satisfy all the following conditions.

• $0\le A_i < 2^M$ $(1\le i\le N)$
• $\operatorname{popcount}(A_i\oplus A_j) \le 2$ $(1\le i < j\le N)$

Here, for non-negative integers $x,y$, we denote by $x\oplus y$ the bitwise $\mathrm{XOR}$ operation of $x$ and $y$, and by $\operatorname{popcount}(x)$ the popcount of $x$.

You are given $T$ test cases, so find the answer for each.

What is bitwise $\mathrm{XOR}$ operation? The bitwise $\mathrm{XOR}$ of non-negative integers $A, B$, denoted $A \oplus B$, is defined as follows. When $A \oplus B$ is written in binary, the digit in the $2^k$ ($k \geq 0$) place is $1$ if exactly one of $A, B$ has $1$ in the $2^k$ place when written in binary, and $0$ otherwise. For example, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$).

What is popcount? For a non-negative integer $x$, $\operatorname{popcount}(x)$ is the number of $1$s when $x$ is written in binary. More precisely, for a non-negative integer $x$ such that $\displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace)$, we have $\displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i$. For example, $13$ in binary is 1101, so we have $\operatorname{popcount}(13)=3$.

Constraints

• $1\le T\le 2\times 10^5$
• $2\le N,M < 998244353$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N M

Output

Output $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.