你得到了一张 2 行的表格，其中第一行有 n 列，第二行有 n+1 列，第一行的第一列和第二行第一列对齐，如图示：

现在需要在这一共 2n+1 个格子中都填入一个整数，需要满足：

• 1、填的整数在 $[0,2k−1]$ 之间。
• 2、同一行不能有相同的数，同一列不能有相同的数。
• 3、所有 $2n+1$ 个数的异或和恰好是 $0$.

现在Cuking想问你，有多少种不同的填数方案，由于答案可能很大，你需要输出答案在模 $998 244 353$下的结果。

第一行一个整数 $T(1≤T≤30)$ 表示测试用例数量。

对每个测试用例，输入两个整数 $n,k，1≤n≤10^6,1≤k≤10^9$，和题目中的 $n,k$ 对应。

对每组格式用例，输出一行一个整数表示答案。

$n=1,k=2$ 的 $9$ 种情况如下：