Summing the Delicacy Fractions

CYJian visits the canteen where on the i-th day there are exactly i dishes. For the j-th dish on day i, its delicacy value is given by the fractional part of \(\frac{i}{j}\), i.e., \(\{\frac{i}{j}\} = \frac{i}{j} - \lfloor \frac{i}{j} \rfloor\). Although the value can be fractional, CYJian tastes a bit of every dish, and eventually, he wishes to know the total delicacy value over a range of days.

You are given \(T\) queries. Each query is described by two integers \(A_i\) and \(B_i\) and asks you to compute the sum \[ S = \sum_{i=A_i}^{B_i} \sum_{j=1}^{i} \Bigl\{\frac{i}{j}\Bigr\} \quad (\bmod\; 998244353), \] where the fractional part is defined in the usual way. Note that \(\{\frac{i}{j}\} = \frac{i \bmod j}{j}\).

Since the answer is a rational number, you are required to compute it in the finite field modulo \(998244353\). It is guaranteed that the operations of division can be performed by using modular inverses (computed as \(j^{998244351} \bmod 998244353\)).

inputFormat

The first line contains a single integer \(T\) indicating the number of queries. Each of the next \(T\) lines contains two integers \(A_i\) and \(B_i\) (with \(1 \le A_i \le B_i\)) representing a query.

outputFormat

For each query, output a single integer — the value of \(S\) modulo \(998244353\).

sample

1
1 1

0