Description

团体程序设计天梯赛即将在南京晓庄学院举行。作为本次比赛的机房座位安排负责人，Albert_Li 又遇到了一个新的问题。

本次比赛使用的机房比较特殊，机房中的座位恰好排成 $2$ 行 $n$ 列，共有 $2n$ 个座位。

本次比赛共有 $a$ 所学校参加，每所学校均有足够多的参赛学生。Albert_Li 需要为每个座位指定一所学校，并安排一名来自该学校的学生坐在这个座位上。

为了促进不同学校选手之间的交流，Albert_Li 希望满足下面的要求：

• 任意两个上下或左右相邻的座位，都不能安排来自同一所学校的学生。

两个座位只有在它们共享一条边时才认为相邻。

本题中只考虑每个座位上学生所属的学校，不区分同一学校的不同学生。因此，只要存在至少一个座位所安排的学校不同，就认为是两种不同的方案。

由于方案数可能非常大，请你计算合法方案数对 $998244353$ 取模后的结果。

Format

Input

第一行给出一个正整数 $T(1\le T\le 2\times10^5)$，表示测试数据的组数。

接下来 $T$ 行，每行给出两个正整数 $n,a(1\le n\le10^{18},1\le a\le10^9)$，分别表示机房的列数和参加比赛的学校数量。

Output

对于每组测试数据，在一行中输出一个整数，表示合法座位安排方案数对 $998244353$ 取模后的结果。

Samples

4
1 3
3 2
3 3
10 4

6
2
54
484243284

11
1 1
1 2
1 3
2 2
3 2
2 3
3 3
1 998244353
2 998244354
3 998244355
10 4

0
2
6
2
2
18
54
0
0
2
484243284

Note

对于第一组数据，机房只有一列，即上下两个座位不能来自同一所学校。

第一个座位有 $3$ 种选择，第二个座位有 $2$ 种选择，因此共有 $3\times2=6$ 种合法方案。