Spartan 家族正在玩一个早教数字表格游戏。游戏在一个两行 $n$ 列的表格上进行。Dante 叔叔负责填充第一行，Vergil 父亲负责填充第二行。他们想让 Nero 计算出有多少种填充方案，使得表格中所有数字的按位异或和为 0。请注意，表格中的数字不能随意填充。Dante 叔叔和 Vergil 父亲在每个单元格中只能填入范围在 $[0, 2^k)$ 内的非负整数。此外，同一行或同一列中不能有重复的数字。现在，他们想问 Nero 有多少种可能的填充方案。Nero 不想回答这个问题；他只想去陪伴 Kyrie。他把这个问题留给你来解答。

输入格式

第一行包含一个正整数 $T(1 \le T \le 10)$，表示测试用例的数量。 接下来有 $T$ 行，每行包含两个正整数 $n$ 和 $k$，其中 $1 \le n \le 40$ 且 $1 \le k \le 10000$。

输出格式

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

样例

样例输入 1

4
1 1
2 1
2 2
3 3

样例输出 1

0
2
36
8736