Problem Description

The Spartan family is playing an early education number table game. The game is played on a table with two rows and $n$ columns. Uncle Dante fills the first row, while Father Vergil fills the second row. They want Nero to calculate how many arrangements are possible so that the bitwise XOR sum of all the numbers is $0$. Please note that the numbers in the table cannot be filled arbitrarily. Uncle Dante and Father Vergil can only fill nonnegative integers from the range $[0, 2^k)$ in each table cell. Moreover, there should be no repeated numbers in the same row or column. Now, they want to ask Nero how many possible arrangements exist to fill the table. Nero doesn't want to answer this question; he just wants to go and accompany Kyrie. He leaves the question for you to answer.

Input

The first line contains only one positive integer $T$$(1\leq T \leq 10)$. which represents the number of test cases.

Next, there will be $T$ lines, each containing two positive integers, $n$ and $k$, where $1 \leq n \leq 40$ and $1 \leq k \leq 10000$.

Output

For each test case, output one line containing an integer representing the answer mod $998244353$.

4
1 1
2 1
2 2
3 3

0
2
36
8736