结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

年会的礼品台设在校礼堂东侧。台面上从左到右排开 $n$ 个摆放位，位置按 $1 \sim n$ 编号；台面下层的储物格里备着 $n$ 个礼盒，礼盒同样按 $1 \sim n$ 编号，编号相同的礼盒与位置是配好对的。布场时，工作人员把礼盒 $i$ 放在位置 $i$ 上，每个位置放一个礼盒。

抽奖环节开始前，工作人员重新摆放了全部礼盒：每个位置恰好放着一个礼盒，每个礼盒恰好占着一个位置。两套摆法被认为不同，当且仅当至少有一个位置上放的礼盒编号不同。程老师在核对礼品台时，把"位置 $j$ 上摆着的礼盒编号正好是 $j$"这一情形记为一次回位。

程老师想知道：若重新摆放后恰好有 $k$ 个礼盒回位，符合要求的摆法有多少种。摆法数可能很大，只需给出它对 $998244353$ 取模后的结果。程老师给出 $q$ 组 $n$ 与 $k$，请依次回答。

输入格式

从文件 giftbox.in 中读入数据。

• 第一行一个整数 $q$，表示询问组数；
• 接下来 $q$ 行，每行两个整数 $n, k$，含义如题面所述。

输出格式

输出到文件 giftbox.out 中。

输出 $q$ 行，每行一个整数，第 $i$ 行是第 $i$ 组询问的答案，即摆法数对 $998244353$ 取模的结果。

样例

2
3 1
4 0

3
9

样例 1 解释

第一组 $n = 3, k = 1$：先在 $3$ 个位置里挑出有礼盒回位的那一个，有 $3$ 种挑法；剩下两个礼盒要都不在原位，只能彼此互换，只有一种摆法；共 $3 \times 1 = 3$ 种。

第二组 $n = 4, k = 0$：四个礼盒都不能摆在自己编号对应的位置上，分两种情形。若礼盒 $1$ 与另一个礼盒互换去向——礼盒 $1$ 摆到那个礼盒的位置上、那个礼盒摆到位置 $1$ 上——则剩下两个礼盒也只能互换；与礼盒 $1$ 互换的礼盒有 $3$ 种选法，共 $3$ 种。若四个礼盒首尾相接地绕成一圈错送——礼盒 $1$ 摆到某个礼盒的位置上，那个礼盒再摆到下一个礼盒的位置上，绕一整圈后回到位置 $1$——则从礼盒 $1$ 起按这一圈的次序读过去，后面三个礼盒的先后次序可以任取，共 $3 \times 2 \times 1 = 6$ 种。两部分相加得 $9$ 种。

2
4 1
4 4

8
1

样例 2 解释

第一组 $n = 4, k = 1$：挑出回位的那个礼盒有 $4$ 种挑法；剩下 $3$ 个礼盒都不能在原位，先定下其中一个礼盒的去向——它只能去另外两个礼盒的位置之一，有 $2$ 种选法，它的去向确定后其余两个礼盒的摆法也随之确定；共 $4 \times 2 = 8$ 种。

第二组 $n = 4, k = 4$：四个礼盒全部回位，即布场时的那一套摆法，只有 $1$ 种。

数据范围

对于所有测试数据，保证：

• $1 \le q \le 10^5$；
• $1 \le n \le 10^6$，$0 \le k \le n$。

各测试点的约束如下：

• 特殊性质 A：每组询问都满足 $k = 0$。
• 特殊性质 B：每组询问都满足 $k = n$。