E. Zero
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

An integer sequence $$$a_1,a_2,\cdots,a_n$$$ is called a zero sequence if and only if it satisfies the following conditions:

  • For $$$i=1,2,\cdots,n-1$$$, $$$a_i \neq a_{i+1}$$$.
  • The binary XOR sum of $$$a_1,a_2,\cdots,a_n$$$ is $$$0$$$, i.e., $$$$$$ \bigoplus_{i=1}^{n}a_i=0 $$$$$$

Given $$$n$$$ and $$$m$$$, find the number of zero sequences of length $$$n$$$ where each element is chosen from the set $$$\{0,1,2,\cdots,2^m-1\}$$$.

Input

The first line contains a positive integer $$$T$$$ $$$(1 \leq T \leq 10^4)$$$, indicating the number of test cases.

For each test case, one line contains two integers $$$n,m$$$ $$$(1\leq n\leq 10^9,0\leq m\leq 10^9)$$$, representing the length of the sequence and the binary length of the sequence elements, respectively.

Output

For each test case, output one integer representing the answer modulo $$$998244353$$$.

Example
Input
5
1 3
2 3
3 3
4 3
5 3
Output
1
0
49
392
2401