zzq 有若干包硬币，每包中有 $k$ 个硬币。有一包装的全是假硬币，其他包中装的均为真硬币。假硬币和真硬币除了重量都一样，假硬币更重，硬币重量是正实数。
zzq 有一个电子天平，可以用它打算进行 $m$ 次称量。形式化地，每次称量时， zzq 可以指定两个交为空的硬币集合 $A$ 和 $B$ ，天平会称出 $W(A)-W(B)$ 的精确值，其中 $W(A)$ 表示 $A$ 集合中的硬币质量和。称量的硬币可以来自任何的包。
zzq 比较懒，所以他希望你帮忙给出一个不超过 $m$ 次称量的称量计划，来确定哪一包装的是假硬币。你给出的称量计划必须是固定好的（即指定好了 $2 m$ 个称量的硬币集合），并且一定可以唯一推断出装有假硬币的包。
编到这里，zzq 终于想起了没指定硬币的包数，所以他希望你输出能解决的最大硬币包数，对 998244353 取模输出。称量计划就不用输出了。
Input
第一行一个正整数 $T$ ，表示数据组数。 接下来 $T$ 行每行两个整数 $m, k$ ，表示一组数据。
Output
输出 $T$ 行，每行表示这组数据中能分辨出的最多的硬币包数，对 998244353 取模输出。
Examples
Input
4 1 1 2 1 2 2 23 45
Output
3 9 17 648619844
对于第一组数据，我们可以称量前两个硬币，如果重量不同重的就是假币，否则剩下的就是假币。
关于第四组数据，我有一个绝妙的解释，只是这里空白太小，写不下。
Notes
对于所有数据， $1 \leq m, k \leq 10^{5}, T \leq 10$ 。
- Subtask 1 (20 pts)：$k=1$ 。
- Subtask 2 (20 pts)：$m, k \leq 3$ 。
- Subtask 3 (30 pts)：$m, k \leq 100$ 。
- Subtask 4 (30 pts)：无特殊限制。