P17732 [ICPC 2019 Xuzhou R] Cats line up

Today, you come to a cat village. There are $N$ cats in this village. Each **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?

The first line contains an integer $T$ indicating the number of $N, K$ you needto 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$

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$.