/ 
Time Limit: 6 sec / Memory Limit: 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).