← 返回题目列表

AtCoder · arc160_b

B. 三对

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

给你一个正整数 N.

求模数 998244353,正整数三元组 (x,y,z) 满足以下条件。

  • 全部 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

在第一个测试用例中, N=1。有一个三元组 (x,y,z) 满足条件: (1,1,1).

在第二个测试用例中, N=2。有四个三元组 (x,y,z) 满足条件: (1,1,1),(2,1,1),(1,2,1),(1,1,2).