题目背景

这个题目没有背景，因为我是圣人的同时还是神之右席。

题目描述

定义一次石子合并的过程如下：有一排 $n$ 堆石子，每一堆有 $a_i(a_i\ge1)$ 个。每次你可以选择相邻的两堆石子合并，设个数分别为 $x,y$，则你会得到一堆 $(x+y)$ 个石子，同时你要付出 $xy$ 的代价。最后要把所有石子合并成一堆。记 $f(a_1,\ldots,a_n)$ 为合并这些石子的最小代价。

给出石子总数 $S$，求

答案对 $998244353$ 取模。

输入格式

本题有多组测试数据。

第一行一个整数 $T$，表示测试数据的数量。
接下来 $T$ 行，每行两个整数，分别为 $n,S$。

输出格式

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

3
2 6
3 5
4 7

35
45
336

5
182565 710825096
429580 541341177
741770 757408347
461909 941427258
114514 1919810

487324711
256967112
352532743
962265551
926494516

提示

【样例解释】

对第一个样例的第一组数据解释：
划分有 $(1,5),(2,4),(3,3),(4,2),(5,1)$，共 $5$ 种。
答案为 $1\times 5 + 2 \times 4 + 3 \times 3 + 4 \times 2 + 5 \times 1 = 35$。

【数据范围】

对于 $100\%$ 的数据，有 $1\le T\le5$，$1\le n\le10^6$，$1\le S\le10^9$。