Arona 和 Plana 是好朋友，遇到什么事情都可以通过友好地协商解决。

一天上午，Arona 打开冰箱，发现冰箱里竟然只剩下一个草莓牛奶了！她认为 Plana 会抢她的牛奶，于是向 Plana 发起了决斗！决斗内容如下：

Arona 给定一个正整数 $n$，然后随机选取一个 $1, 2, \cdots, n$ 的排列 $a$。令 $L$ 表示满足 $\max\limits_{j=1}^i a_j = a_i$ 的正整数 $i$ 的数量，$R$ 表示满足 $\min\limits_{j=1}^i a_j = a_i$ 的正整数 $i$ 的数量。如果 $L \ge R$，则 Arona 赢，否则 Plana 赢。

Arona 很自信，觉得她自己能轻松获得胜利，为了防止她胜利的时候 Plana 抱怨不公平，她又选了一个正整数 $k \le n$，并且将自己的胜利条件改为了 $L \ge R + k$。

虽然 Plana 一点也不在乎草莓牛奶，但她知道 Arona 能赢的概率不太大。Plana 现在想要知道这个概率具体是多少。屏幕前的你能帮她求出来这个具体值吗？

假设 Arona 能胜利的概率为 $p$，你只需要求出 $p \times n!$ 对 $998244353$ 取模后的结果即可。

Input

此题包含多组测试数据。

第一行输入一个正整数 $T$ $(1 \le T \le 10^3)$，表示测试数据组数。

接下来 $T$ 行，每行输入两个整数 $n, k$ $(1 \le k \le n \le 10^6)$，含义同题目描述。

保证所有测试数据中 $n$ 的总和不超过 $10^6$。

Output

对于每组测试数据，输出一行一个整数，表示所求的答案对 $998244353$ 取模后的结果。

Examples

Input 1

2
3 1
3 2

Output 1

2
1

Input 2

10
5 3
97 31
2468 1357
9876 1
9876 1234
9876 6789
234567 1
234567 234555
234567 123456
234567 12345

Output 2

7
878338345
199045303
782408107
474021604
653690172
358465928
130271340
136329270
679313091

Note

对于第一组数据，$n = 3$ 时共有 $6$ 种排列：

• 数列 $[1, 2, 3]$：$L = 3, R = 1$。
• 数列 $[1, 3, 2]$：$L = 2, R = 1$。
• 数列 $[2, 1, 3]$：$L = 2, R = 2$。
• 数列 $[2, 3, 1]$：$L = 2, R = 2$。
• 数列 $[3, 1, 2]$：$L = 1, R = 2$。
• 数列 $[3, 2, 1]$：$L = 1, R = 3$。

因此，当 $n = 3, k = 1$ 时，有 $[1, 3, 2]$ 和 $[1, 2, 3]$ 满足 $L \ge R + 1$ 的要求；而当 $n = 3, k = 2$ 时，只有 $[1, 2, 3]$ 满足 $L \ge R + 2$ 的要求。