一个整数序列 $a_1, a_2, \dots, a_n$ 被称为零序列，当且仅当它满足以下条件：

• 对于 $i = 1, 2, \dots, n - 1$，$a_i \neq a_{i+1}$。
• $a_1, a_2, \dots, a_n$ 的二进制异或和为 $0$，即： $$\bigoplus_{i=1}^n a_i = 0$$

给定 $n$ 和 $m$，求长度为 $n$ 且每个元素都选自集合 $\{0, 1, 2, \dots, 2^m - 1\}$ 的零序列的数量。

输入格式

第一行包含一个正整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。

对于每个测试用例，一行包含两个整数 $n, m$ ($1 \le n \le 10^9, 0 \le m \le 10^9$)，分别表示序列的长度和序列元素的二进制长度。

输出格式

对于每个测试用例，输出一个整数，表示答案模 $998244353$ 的结果。

样例

输入样例 1

5
1 3
2 3
3 3
4 3
5 3

输出样例 1

1
0
49
392
2401