罗德岛有个 (打扑克) 占卜干员叫做远山，罗德岛已经好久没有得到四号线索了，于是打算请远山占卜。
远山发现如果将一些占卜牌排成一个长度为 2n 的圆环，就可以知晓未来一小时内发生的事情。但前提是我们要给每张占卜牌附上一个魔法属性，占卜阵才能发挥功效，现在远山想要知道自己总共能创造出多少互异的占卜阵，已知罗德岛现有 k 种魔法属性，远山正在构造的占卜阵的长度为 2n，求能够构造出的占卜阵数量
注意，两个占卜阵是同构的当且仅当某个占卜阵旋转后每个位置上的占卜牌属性均与另一个占卜阵一致。此外，由于未来的不稳定性，对角的两个占卜牌交换后相同的两个占卜阵也是同构的。然后由于答案太大，远山只想得到模 19260817 意义下的答案
第一行一个数 T 表示数据组数
接下来 T 行每行两个数 n,k 表示占卜阵的长度为 2n，罗德岛有 k 种魔法属性
输出共 T 行，表示 T 个答案
T <= 2222，1 <= n,k < 19260817