质因数分解

题目描述

$\mathcal {Rubyonly}$ 有很多正整数，他想让你把它们分别分解成若干个质数的和，好让他进行接下来的计算。

一个正整数 $n$ 分解的方案可能有很多种，$\mathcal {Rubyonly}$ 现在只想知道本质不同的方案数有多少个。由于方案数很多，所以 $\mathcal {Rubyonly}$ 只想知道在模 $988244353$ 意义下的答案。

两个分解方案本质不同，当且仅当存在某个质数在两个方案中出现的次数不同。

$\mathcal {Rubyonly}$ 有 $q$ 次询问，每次询问都会给你一个需要分解的正整数 $n$，请你依次告诉他对于每次询问的答案。

输入格式

输入一共 $q + 1$ 行

第 $1$ 行，一个正整数 $q$，表示询问次数

接下来 $q$ 行，每行一个正整数 $n$，表示本次询问需要分解的数

输出格式

输出 $q$ 行

每行一个整数，表示每次询问的答案（在模 $988244353$ 意义下）

样例 #1

样例输入 #1

2
2
9

样例输出 #1

1
4

提示

样例解释

样例一共 $2$ 次询问

对于第 $1$ 次询问， $2$ 仅有 $1$ 个本质不同的分解方案，即分解为 $(2)$

对于第 $2$ 次询问， $9$ 有 $4$ 个本质不同的分解方案，分别为 $(2,2,2,3)$，$(2,2,5)$，$(2,7)$，$(3,3,3)$

数据范围

对于 $20 \%$ 的数据，保证 $n\leq 20$

对于 $40 \%$ 的数据，保证 $n\leq 200$

对于另外 $10 \%$ 的数据，保证 $q = 1$

对于 $100 \%$ 的数据，保证 $1\leq q\leq 10^5$，$2\leq n\leq 5000$