B - Triple Pair Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500500

問題文

正整数 NN が与えられます。

以下の条件を満たす 33 個の正整数の組 (x,y,z)(x,y,z) の個数を 998244353998244353 で割ったあまりを求めてください。

  • xy,yz,zxxy,yz,zx が全て NN 以下である。

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

制約

  • 1T1001 \le T \le 100
  • 1N1091 \le N \le 10^9

入力

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

ここで、casei\mathrm{case}_i とは、ii 番目のテストケースを意味する。

TT
case1\mathrm{case}_1
case2\mathrm{case}_2
\vdots
caseT\mathrm{case}_T

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

NN

出力

TT 行出力せよ。i(1iT)i(1 \le i \le T) 行目には、ii 番目のテストケースに対する答えを出力せよ。


入力例 1Copy

Copy
4
1
2
5
998244353

出力例 1Copy

Copy
1
4
17
727512986

11 個目のテストケースでは、N=1N=1 です。条件を満たす (x,y,z)(x,y,z)(1,1,1)(1,1,1)11 個です。

22 個目のテストケースでは、N=2N=2 です。条件を満たす (x,y,z)(x,y,z) は、(1,1,1),(2,1,1),(1,2,1),(1,1,2)(1,1,1),(2,1,1),(1,2,1),(1,1,2)44 個です。

Score : 500500 points

Problem Statement

You are given a positive integer NN.

Find the number, modulo 998244353998244353, of triples of positive integers (x,y,z)(x,y,z) that satisfy the following condition.

  • All of xyxy, yzyz, zxzx are less than or equal to NN.

You have TT test cases to solve.

Constraints

  • 1T1001 \le T \le 100
  • 1N1091 \le N \le 10^9

Input

The input is given from Standard Input in the following format, where casei\mathrm{case}_i represents the ii-th test case:

TT
case1\mathrm{case}_1
case2\mathrm{case}_2
\vdots
caseT\mathrm{case}_T

Each test case is in the following format:

NN

Output

Print TT lines. The ii-th line (1iT)(1 \le i \le T) should contain the answer for the ii-th test case.


Sample Input 1Copy

Copy
4
1
2
5
998244353

Sample Output 1Copy

Copy
1
4
17
727512986

In the first test case, N=1N=1. There is one triple (x,y,z)(x,y,z) that satisfies the condition: (1,1,1)(1,1,1).

In the second test case, N=2N=2. There are four triples (x,y,z)(x,y,z) that satisfy the condition: (1,1,1),(2,1,1),(1,2,1),(1,1,2)(1,1,1),(2,1,1),(1,2,1),(1,1,2).



2025-01-04 (Sat)
21:39:38 +00:00