#P18756. [2027年国家集训队互测] Set

[2027年国家集训队互测] Set

Set

题目描述

给定正整数 mm,称一个正整数集 SS 是好的当且仅当 ∀x∈S\forall x\in S,若正整数序列 a1∼ama_{1}\sim a_m 满足 ∑i=1mai=x\sum_{i=1}^m a_i=x,则 ∏i=1mai∈S\prod_{i=1}^m a_i\in S。求好的集合的个数对 998244353998244353 取模的结果。

集合 SS 可以是无限集。

输入格式

第一行一个正整数 TT,表示数据组数。

后面 TT 行每行一个正整数表示题目描述中的 mm。

输出格式

输出 TT 行,每行一个整数表示答案。

样例

样例输入

3
2
3
4

样例输出

6
15
22

样例解释

当 m=2m=2 时,SS 可能为 $\emptyset,\{1\},\{1,2\},\{1,2,3\},\{1,2,3,4\},\mathbb{N^*}$。

数据范围

保证除样例外数据组数 T=5T=5。

保证 m≥2m\ge 2。

子任务 分值 数据范围 特殊性质
1 12 m≤10m\le 10 无
2 10 m≤1000m\le 1000
3 8 m≤105m\le 10^5 m≡0(mod2)m\equiv 0\pmod 2
4 无
5 m≤3×106m\le 3\times 10^6 m≡0(mod2)m\equiv 0\pmod 2
6 12 无
7 8 m≤4×108m\le 4\times 10^8 m≡0(mod2)m\equiv 0\pmod 2
8 17 无
9 m≤109m\le 10^9

开启了一些合理的子任务依赖。

样例附件