Description

You have $n!$ permutations of length $n$ sorted in lexicographical order.

Among the first $S$ permutations in this order, find a permutation $p$ that maximizes $\displaystyle\sum_{i=1}^n\sum_{j=1}^{i}p_j$. Output this maximum value modulo $998244353$.

Input Format

The first line contains an integer $T$.

Each of the next $T$ lines contains two integers $n$ and $S$.

Output Format

For each query, output one integer representing the maximum value modulo $998244353$.

1
4 5

23

Hint

Explanation for Sample #1

The first five permutations of length $4$ are:

• $1, 2, 3, 4 \to 1 + (1+2) + (1+2+3) + (1+2+3+4) = 20$
• $1, 2, 4, 3 \to 1 + (1+2) + (1+2+4) + (1+2+4+3) = 21$
• $1, 3, 2, 4 \to 1 + (1+3) + (1+3+2) + (1+3+2+4) = 21$
• $1, 3, 4, 2 \to 1 + (1+3) + (1+3+4) + (1+3+4+2) = 23$
• $1, 4, 2, 3 \to 1 + (1+4) + (1+4+2) + (1+4+2+3) = 23$

The maximum value is $23$.

Constraints

This problem uses bundled tests. You must pass all test cases in a subtask to receive points.

For $100\%$ data: $1 \le T \le 10^5$, $1 \le n \le 10^9$, $1 \le S \le \min(n!,\ 10^{18})$.

Translated by DeepSeek R1