Background

This problem has no background, because I am a saint and also the right seat of god.

Problem Description

Define a process of merging stones as follows: there is a row of $n$ piles of stones, and the $i$-th pile has $a_i(a_i\ge1)$ stones. Each time, you may choose two adjacent piles to merge. Suppose their sizes are $x,y$, then you will get one pile of $(x+y)$ stones, and you need to pay a cost of $xy$. In the end, all piles must be merged into one pile. Let $f(a_1,\ldots,a_n)$ be the minimum cost to merge these piles of stones.

Given the total number of stones $S$, compute

and output the answer modulo $998244353$.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, the number of test cases.
The next $T$ lines each contain two integers $n,S$.

Output Format

Output $T$ lines, each containing one integer, the answer modulo $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

Hint

[Sample Explanation]

Explanation for the first test case in the sample:
The partitions are $(1,5),(2,4),(3,3),(4,2),(5,1)$, for a total of $5$ cases.
The answer is $1\times 5 + 2 \times 4 + 3 \times 3 + 4 \times 2 + 5 \times 1 = 35$.

[Constraints]

For $100\%$ of the testdata, $1\le T\le5$, $1\le n\le10^6$, $1\le S\le10^9$.

Translated by ChatGPT 5