/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
正整数 N が与えられます。
以下の条件を満たす 3 個の正整数の組 (x,y,z) の個数を 998244353 で割ったあまりを求めてください。
- xy,yz,zx が全て N 以下である。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1 \le T \le 100
- 1 \le N \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
ここで、\mathrm{case}_i とは、i 番目のテストケースを意味する。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる。
N
出力
T 行出力せよ。i(1 \le i \le T) 行目には、i 番目のテストケースに対する答えを出力せよ。
入力例 1
4 1 2 5 998244353
出力例 1
1 4 17 727512986
1 個目のテストケースでは、N=1 です。条件を満たす (x,y,z) は (1,1,1) の 1 個です。
2 個目のテストケースでは、N=2 です。条件を満たす (x,y,z) は、(1,1,1),(2,1,1),(1,2,1),(1,1,2) の 4 個です。
Score : 500 points
Problem Statement
You are given a positive integer N.
Find the number, modulo 998244353, of triples of positive integers (x,y,z) that satisfy the following condition.
- All of xy, yz, zx are less than or equal to N.
You have T test cases to solve.
Constraints
- 1 \le T \le 100
- 1 \le N \le 10^9
Input
The input is given from Standard Input in the following format, where \mathrm{case}_i represents the i-th test case:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is in the following format:
N
Output
Print T lines. The i-th line (1 \le i \le T) should contain the answer for the i-th test case.
Sample Input 1
4 1 2 5 998244353
Sample Output 1
1 4 17 727512986
In the first test case, N=1. There is one triple (x,y,z) that satisfies the condition: (1,1,1).
In the second test case, N=2. There are four triples (x,y,z) that satisfy the condition: (1,1,1),(2,1,1),(1,2,1),(1,1,2).