Problem Statement

You are given integers $N$ and $X$. Assume that an integer sequence $A = (A_1, \ldots, A_N)$ satisfies all of the conditions below.

• $A_1 = X$.
• For every $i$ ($1\leq i\leq N$), $A_i$ is a multiple of $i$.
• $A$ is strictly increasing. In other words, $A_1 < \cdots < A_N$ holds.

Find the minimum possible value of $\sum_{i=1}^N A_i$, modulo $998244353$.

There are $T$ test cases, each of which should be solved.

Constraints

• $1\leq T\leq 10$
• $1\leq N \leq 10^{18}$
• $1\leq X \leq 10^{18}$

Input

Input is given from Standard Input from the following format:

T
\text{case}_1
\vdots
\text{case}_T

Each case is in the following format:

N X

Output

Print $T$ lines. The $i$-th line should contain the answer for $\text{case}_i$.