Problem Description

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

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

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

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

Input

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

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

Output

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

2
1 2
114 514

9
410645142

Hint

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