Problem Description

Xiao Lan originally had a set of cards, with the numbers $1, 2, \ldots, n$ written on them, exactly one card for each number.

Later, Xiao Lan found that $L$ consecutive cards were missing from this set. That is, there exists a positive integer $a$ such that the cards numbered $a, a+1, \ldots, a+L-1$ are all missing, where $a+L-1 \le n$.

After the loss happened, Xiao Lan added up the numbers on all remaining cards, and the total sum is $S$.

Now, given the sum $S$ of the remaining cards and the number $L$ of missing cards, please compute the sum of all possible original total counts $n$ of cards. If there is no $n$ that satisfies the conditions, the answer is $0$. The same valid $n$ is counted only once even if it corresponds to multiple ways of losing cards.

Since the answer may be very large, you only need to output the sum of all such $n$ modulo $998244353$.

Input Format

The first line contains a positive integer $T$, indicating the number of queries.

The next $T$ lines each contain two positive integers $S$ and $L$, separated by a space.

Output Format

Output $T$ lines. Each line contains one integer, representing the sum of all possible $n$ for the corresponding query modulo $998244353$.

4
10 2
15670 27
20 3
35 1

11
579
0
8

Hint

Sample Explanation

For the first query, $S = 10, L = 2$.

• When $n = 5$, it is possible to lose the two cards numbered $2, 3$, and the sum of the remaining card numbers is $10$.
• When $n = 6$, it is possible to lose the two cards numbered $5, 6$, and the sum of the remaining card numbers is $10$.

Therefore, the possible values of $n$ are $5$ and $6$, and the answer is $5 + 6 = 11$.

Constraints and Notes

For $30\%$ of the testdata, $1 \le T \le 5$, $1 \le S \le 10^6$, $1 \le L \le 20$.

For all testdata, $1 \le T \le 10^5$, $1 \le S \le 10^{18}$, $1 \le L \le 100$.

Translated by ChatGPT 5