题目背景

『我喜欢雪。』

『之前虽然讨厌寒冷，现在却是最喜欢了。』

题目描述

Rikka 给了你 $T$ 组询问，每组询问给定两个正整数 $n,k$，你需要告诉 Rikka 有多少个长度为 $n$ 的排列 $\pi$ 满足如下条件：

• $\pi_1<\pi_2$

• $\pi_{n-1}>\pi_{n}$

• 恰好存在 $k$ 个位置 $i(2\leq i\leq n-1)$ 满足 $\pi_{i-1}<\pi_{i}$ 且 $\pi_{i}>\pi_{i+1}$。

答案对 $998244353$ 取模。

输入格式

第一行两个整数 $T,r$，表示询问次数以及 $n$ 的值域。

接下来 $T$ 行，每行两个整数 $n,k$，意义如题意所示。

输出格式

$T$ 行，每行一个正整数，表示答案对 $998244353$ 取模的值。

2 10
3 1
5 2

2
16

提示

样例解释 1

对于第一组询问，$n=3,k=1$，$(1,3,2)$ 和 $(2,3,1)$ 均满足条件，答案为 $2$。

对于第二组询问，满足条件的排列为：

$$(1,3,2,5,4),(1,4,2,5,3),(1,4,3,5,2),(1,5,2,4,3),(1,5,3,4,2)\\(2,3,1,5,4),(2,4,1,5,3),(2,4,3,5,1),(2,5,1,4,3),(2,5,3,4,1)\\(3,4,1,5,2),(3,4,2,5,1),(3,5,1,4,2),(3,5,2,4,1),(4,5,1,3,2),(4,5,2,3,1) $$

共 $16$ 个，所以答案为 $16$。

数据范围

子任务编号	分值	$T\leq$	$r\leq$	其他限制
Subtask 1	$1$		$10$
Subtask 2	$5$	$2\times 10^5$
Subtask 3	$13$	$1$	$2\times 10^3$
Subtask 4		$2\times 10^5$
Subtask 5	$16$		$2\times 10^5$	$k=\lfloor\frac{n-1}{2}\rfloor$ 且 $n$ 为奇数
Subtask 6				$k=\lfloor\frac{n-1}{2}\rfloor-1$
Subtask 7	$36$

对于 $100\%$ 的数据，$1\leq T\leq 2\times 10^5,3\leq n\leq r\leq 2\times 10^5,\max(1,\lfloor\frac{n-1}{2}\rfloor-10)\leq k\leq \lfloor\frac{n-1}{2}\rfloor$。