← 返回题目列表

AtCoder · pakencamp_2025_day3_r

R. 具有下限的子树

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

配点 : 100 点

致环球杯参赛者

当包含在 Universal Cup 中时,此问题将被删除。因此,当使用 AtCoder 结果进行 Universal Cup 时,我们建议先解决其他问题。 给出了


問題文

正整数 N 。

在顶部 编号为 1 如果要将其更改为输出最多为 N 的顶点 1 是一棵有根树,其根满足以下条件: 除以 998244353 求余数。 组成

  • 頂点 i(1 \leq i \leq N) 子树的顶点个数均为 i 就是这样。

但是, 2 两棵树的根不同。 2 一对顶点 u,v(1 \leq u,v \leq N) 存在,并且在一棵有根树中 u,v 这意味着在两者之间粘贴了一条边,但在另一根有根树上没有粘贴边。

1 对于每个输入, 请解决 T 测试用例。

制約

  • 1 \leq T \leq 5 \times 10^{5}
  • 1 \leq N \leq 5 \times 10^{5}
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

T
\mathrm{case}_{1}
\mathrm{case}_{2}
\vdots
\mathrm{case}_{T}

每个测试用例均按以下格式给出。 打印

N

出力

T 行。 i 在线 \mathrm{case}_{i} 的答案。


入力例 1

3
4
1
1000

出力例 1

6
1
815987315

该输入包含 包含 3 测试用例。