Safety First
一架梯子由 n 段组成,每段长度都是正整数,且从左到右非递增。记各段长度为 d1,d2,…,dn,则
d1≥d2≥⋯≥dn≥1.
梯子竖立后的高度,是最高点和最低点的高度差。下图表示梯子的分段和高度 m:

小 Q 需要一架高度恰好为 m 的稳定梯子。稳定要求:
- 第一段的下端接触地面;
- 对每个 i=1,2,…,n−1,第 i 段的上端必须锁定在第 i+1 段的上端或下端。
下图左侧的连接不稳定;中间和右侧分别表示锁定在下一段上端、下端的两种稳定连接:

求长度为 n 段、高度恰好为 m 的不同稳定梯子数量,对 998244353 取模。
如果某一段的长度不同,或者某对相邻段的锁定方式不同,就视为两架不同的梯子。即使各段长度完全相同,不同锁定方式也可能对应不同梯子。
输入格式
第一行包含整数 T,表示询问数量。
接下来 T 行,每行包含两个整数 n,m。
输出格式
对每个询问输出一行,包含一个整数,表示答案对 998244353 取模的结果。
数据范围
- 1≤T≤105;
- 1≤n,m≤2000。
本题没有额外的询问总规模限制。
样例 1
3
1 3
2 3
3 3
1
4
10
样例 2
1
2000 2000
204576309
样例说明
在样例 1 中:
- (n,m)=(1,3):唯一的梯子只有一段,长度为 3。
- (n,m)=(2,3):段长分别可以是 [2,1]、[3,1]、[3,2]、[3,3]。第一种把第一段上端接到第二段下端,后三种接到第二段上端。
- (n,m)=(3,3):十种方案的段长为 [1,1,1]、[2,1,1]、[2,1,1]、[2,2,1]、[3,1,1]、[3,2,1]、[3,2,2]、[3,3,1]、[3,3,2]、[3,3,3]。其中两份 [2,1,1] 的锁定方式不同:分别让第二段或第三段向总高度贡献其长度。