E - Sequence of Multiples 解説 /

実行時間制限: 6 sec / メモリ制限: 1024 MB

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

入力例 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)。

Score : 800 points

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.

Sample Input 1

5
5 100
1 10
10 1
1000000000000000000 1
100 100

Sample Output 1

525
10
55
75433847
61074

Here is a sequence A that minimizes \sum_{i=1}^N A_i for each of the first three test cases.

  • The first test case: A = (100, 102, 105, 108, 110).
  • The second test case: A = (10).
  • The third test case: A = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10).