[入门赛 #9] 最澄澈的空与海 (Hard Version)

材料 1： > 请小心地计算下面的算式：$138 - 108 \div 6 = ?$ > 你大概难以置信，这个算式的计算结果竟然是 $5!$ 材料 2： > 对于一个正整数 $x$，$x! = 1 \times 2 \times \cdots \times (x - 1) \times x$。我们称 $x!$ 为 $x$ 的阶乘。 > 特别的，$0! = 1$。 显然，「$138 - 108 \div 6 = 5$」是错误的，而「$(138 - 108) \div 6 = 5$」是正确的，所以对材料 1 中的内容，部分读者会认为「作者没有搞清加减乘除的运算优先级关系而犯错」。 然而，材料 1 最后一行的叹号并不是标点符号，而是材料 2 提到的「阶乘」。 考虑到这一点，「$138 - 108 \div 6 = 5! = 1 \times 2 \times \cdots \times 5 = 120$」显然就是正确的了。

然而，此题可能与上面的题目背景关系不是很大。 我们会给你 $T$ 组数据，每组数据包括一个正整数 $n$。 对于每组数据，请你帮助求出满足以下条件的整数三元组 $(x, y, z)$ 的组数： 1. $x \geq 0$，$z \geq 1$。 2. $x - y \div z = n!$ 且 $(x - y) \div z = \dfrac{n!}{n}$。 由于答案可能过大，因此你需要输出答案对 $998244353$ 取模后的结果。 不难注意到答案有可能为 $\infty$，这时请按照「输出格式」要求进行处理。 **请注意此处应满足 $(x - y) \div z = \dfrac{n!}{n}$ 而不是 $= n$。** 请注意这里的 $\div$ 不是向下取整的整除，这显然意味着你需要保证 $y \div z$ 和 $(x - y) \div z$ 为整数。

输入共 $T + 1$ 行。 第一行为一个整数 $T$。 接下来 $T$ 行，每行一个整数 $n$。

输出共 $T$ 行，每行一个整数或一个字符串。 对第 $i$ 行，如果对于输入数据中第 $i + 1$ 行的 $n$，满足 $x - y \div z = n!$ 且 $(x - y) \div z = \dfrac{n!}{n}$ 的整数三元组 $(x, y, z)$ 有无限个，则输出一行 `inf`，否则输出满足条件的三元组的数量对 $998244353$ 取模后的结果。

3
2
3
4

1
3
6

### 样例 1 解释 样例中的具体三元组如下： | $n$ | 所有可能的三元组 | | :----------: | :----------: | | $2$ | $(2, 0, 2)$ | | $3$ | $\begin{matrix}(8, 4, 2) & (5, -5, 5) & (6, 0, 3)\end{matrix}$ | | $4$ | $\begin{matrix}(19, -95, 19) & (21, -21, 7) & (24, 0, 4) \\ (27, 9, 3) & (20, -40, 10) & (36, 24, 2)\end{matrix}$ | ### 数据规模与约定 对于前 $20\%$ 的数据，保证 $T \leq 10$，$n \leq 10$。 对于前 $40\%$ 的数据，保证 $n \leq 10 ^ 3$。 对于另外 $20\%$ 的数据，保证 $T = 1$。 对于 $100\%$ 的数据，保证 $1 \leq T \leq 10 ^ 5$，$1 \leq n \leq 10 ^ 6$。