Today, you come to a cat village. There are $N$ cats in this village. Each \textbf{cat is very cute}, and all the $N$ cats are very cleverly and, they line up in a row.

The cats in this village are very special!!! Why do I say that? Because the heights of these cats are unique, and they are all integer numbers between $1$ and $N$(both inclusive).

As we all know, everyone dislikes standing next to someone who is too tall when taking pictures, because standing next to such a person would make you look short. Humans are like this, and so are cats.

Every cat wants the difference in the height of the cat standing next to it to be no more than $K$. A cat would be happy if the difference in the height between it and each of its neighbor(s) is no more than $K$.

Now, given the number of cats in this village and the height difference $K$ that the cat can accept, could you calculate that how many ways can the cats line up to make all of them happy?

Input

The first line contains an integer $T$ indicating the number of $N, K$ you need to calculate. The following $T$ lines each line contains two integers $N, K$.

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

  Output

For each test case, output one line containing one integer $x$ --- the number of ways the cats can line up to make all of them happy modulo $998244353$.

Sample Input 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

Sample Output 1

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