E-牛牛与序列_牛客挑战赛39

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛擅长处理各种序列计数。今天他盯上了反复♂横跳序列。
若一个长度为 $n\ (n\ge 3)$ 的数列 $a_1, a_2, \cdots , a_n$ 满足：同时存在两个 $i,j\ (1<i,j\leq n)$ ，使得 $a_{i-1}<a_i,a_{j-1}>a_j$ ，则这个序列是反复♂横跳序列。
牛牛想知道，所有长度为 $n$ ，同时对 $\forall 1\leq i\leq n,1\leq a_i\leq k$ 的反复♂横跳序列有多少个。由于这个数可能很大，你只需要输出它对 $998244353$ 取模的结果。

输入描述:

本题有多组数据。
输入第一行一个数，表示数据组数。
接下来行，每行两个数，表示一组数据。不同组数据之间是独立的。对于每一组数据，你都要分别计算出一个结果。

输出描述:

输出行，每行一个数字，依次表示这组数据的答案。最后的答案需要对取模。

示例1

输入

复制

2
3 2
3 3

输出

复制

2
10

说明

对于第一组数据，满足条件的序列只有两个:。
对于第二组数据，满足条件的序列有十个:。

备注:

数据满足。对于单组数据，。对于所有数据，保证。