P17732 [ICPC 2019 Xuzhou R] Cats line up

今天，你来到了一个猫村。这个村子里有 $N$ 只猫。每只**猫都非常可爱**，并且所有 $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$ 取模的结果。

翻译由 DeepSeek V4 Pro 完