#17 「 押题 」

统计

为了备战noip,dwj在前一天晚上熬夜押题,试图压中noip第一题:

跳蚤工厂里有一排$n$个开关,每个开关有两个状态,开的状态会产生一个耗电量的代价$a_i$, 关的时候会导致对应的机器停止运转损失代价$b_i$。如果第$i$个开关和前一个开关状态一样,还会付出一个代价$c_i$。

现在请你选择每个开关的状态,最小化总代价。数据中$0 \leq a_i, b_i, c_i \leq w$。 (warning:虽然$c_1$没有用,但是还是会出现在本题输入数据中)

dwj押了题之后,开始在草稿纸上暴力枚举每种可能的数据手动分类讨论。

他在草稿纸上写出了所有可能的数据之后,把他们的答案加了起来,请问这个数是多少呢?请输出它对$998244353$取膜的值。

输入格式

第一行一个整数$T$表示数据组数和题目参数。

接下来$T$行,每行两个整数$n, w$。

输出格式

一行一个整数表示答案。

样例数据

input

5
3 4 
6 6
5 3
10 10
50 10

output

8404360
24543892
850131011
858563900
240195664

数据规模与约定

$T \leq 300, 1 \leq w \leq 10, 1 \leq n \leq 50$

时间限制:1s

空间限制:512MB

Author: whx