#1991. Set

    ID: 1991 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>CTT赛事:contest4599来源:qoj.ac数据:公开样例动态规划数学

Set

Set

题目描述

标题: Set - Problem - QOJ.ac

#21430. Set

Statistics

题目描述

给定正整数 m,称一个正整数集 S 是好的当且仅当 ∀x∈S,若正整数序列 a1∼am 满足 ∑i=1mai=x,则 ∏i=1mai∈S。求好的集合的个数对 998244353 取模的结果。

输入格式

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

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

输出格式

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

样例

输入

3
2
3
4

输出

6
15
22

样例解释

当 m=2 时,S 可能为 ∅,{1},{1,2},{1,2,3},{1,2,3,4},N∗。

数据范围

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

保证 m≥2。

子任务 分值 数据范围 特殊性质 1 12

m≤10

无 2 10

m≤1000

无 3 8

m≤105

m≡0(mod2)

4 8

m≤105

无 5 8

m≤3×106

m≡0(mod2)

6 12

m≤3×106

无 7 8

m≤4×108

m≡0(mod2)

8 17

m≤4×108

无 9 17

m≤109

无

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
2
3
4
6
15
22