配点 : $800$ 点

問題文

整数 $N, X$ が与えられます。整数列 $A = (A_1, \ldots, A_N)$ が次の条件をすべて満たすとします。

• $A_1 = X$。
• 任意の $i$ ($1\leq i\leq N$) に対して、$A_i$ は $i$ の倍数である。
• $A$ は狭義単調増加である。つまり、$A_1 < \cdots < A_N$ が成り立つ。

$\sum_{i=1}^N A_i$ として考えられる最小値を、$998244353$ で割った余りを求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

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

入力

入力は以下の形式で標準入力から与えられます。

$T$

$\text{case}_1$

$\vdots$

$\text{case}_T$

各テストケースは以下の形式で与えられます。

$N$ $X$

出力

$T$ 行出力してください。$i$ 行目には、$\text{case}_i$ に対する答えを出力してください。

5
5 100
1 10
10 1
1000000000000000000 1
100 100

525
10
55
75433847
61074

はじめの $3$ つのテストケースについて、例えば次の $A$ が $\sum_{i=1}^N A_i$ の最小値を与えます：

• $1$ 番目のテストケース：$A = (100, 102, 105, 108, 110)$。
• $2$ 番目のテストケース：$A = (10)$。
• $3$ 番目のテストケース：$A = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10)$。