問題文

整数 $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$ に対する答えを出力してください。

入力例 1

5
5 100
1 10
10 1
1000000000000000000 1
100 100

出力例 1

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)$。