今天，你来到了一个猫咪村。这个村子里有 $N$ 只猫。 每只猫都非常可爱，而且这 $N$ 只猫非常聪明，它们排成了一行。

这个村子里的猫非常特别！！！ 为什么这么说呢？因为这些猫的身高各不相同，且都是 $1$ 到 $N$ 之间的整数（包含 $1$ 和 $N$）。

众所周知，在拍照时，每个人都不喜欢站在太高的人旁边，因为站在这样的人旁边会显得自己很矮。 人类如此，猫也是如此。

每只猫都希望与它相邻的猫的身高差不超过 $K$。 如果一只猫与它每一位邻居的身高差都不超过 $K$，那么这只猫就会感到快乐。

现在，给定村子里猫的数量以及猫能接受的身高差 $K$，请你计算有多少种排队方式能让所有的猫都感到快乐？

第一行包含一个整数 $T$，表示你需要计算的 $N, K$ 组数。 接下来的 $T$ 行，每行包含两个整数 $N, K$。

• $1 \le T \le 10^5$
• $1 \le N \le 10^6$
• $1 \le K \le 3$

对于每组测试数据，输出一行，包含一个整数 $x$ —— 表示能让所有猫都感到快乐的排队方式数量，结果对 $998244353$ 取模。

样例

输入格式 1

18
1 1
2 2
3 2
1 3
2 3
3 3
4 3
5 3
6 3
7 3
8 3
9 3
10 3
11 3
12 3
13 3
14 3
15 3

输出格式 1

1
2
6
1
2
6
24
72
180
428
1042
2512
5912
13592
30872
69560
155568
345282