#P18025. Sequence Domination

Sequence Domination

Sequence Domination

一个长度为 NN 的整数序列 VV 称为超递减序列,如果 VN≥0V_N\ge0,且对每个 1≤i<N1\le i<N 都有

Vi≥Vi+1+Vi+2+⋯+VN.V_i\ge V_{i+1}+V_{i+2}+\cdots+V_N.

给定正整数 N,MN,M,求有多少对长度为 NN 的整数序列 (A,B)(A,B) 满足:

  • 对所有 ii,1≤Ai,Bi≤M1\le A_i,B_i\le M;
  • 对每一个长度为 NN 的超递减整数序列 VV,均有
∑i=1NAiVi≥∑i=1NBiVi.\sum_{i=1}^{N}A_iV_i\ge\sum_{i=1}^{N}B_iV_i.

答案对 998244353998244353 取模。

输入格式

第一行一个整数 TT。接下来 TT 行,每行两个整数 N,MN,M,表示一组数据。

输出格式

每组数据输出一行一个整数,表示合法序列对的数量对 998244353998244353 取模后的结果。

数据范围

1≤T≤1001\le T\le100,1≤N,M≤50001\le N,M\le5000。所有测试用例的 NN 之和不超过 50005000,MM 之和也不超过 50005000。

样例 1

输入

4
1 1
2 2
2 1
34 43

输出

1
10
1
711021868