Background

Material 1:

Please carefully compute the following expression: $138 - 108 \div 6 = ?$
You may find it hard to believe that the result of this expression is actually $5!$

Material 2:

For a positive integer $x$, $x! = 1 \times 2 \times \cdots \times (x - 1) \times x$. We call $x!$ the factorial of $x$.
In particular, $0! = 1$.

Obviously, “$138 - 108 \div 6 = 5$” is wrong, while “$(138 - 108) \div 6 = 5$” is correct. So for the content in Material 1, some readers may think “the author made a mistake because they did not understand the priority order of $+$, $-$, $\times$, and $\div$.”

However, the exclamation mark in the last line of Material 1 is not punctuation, but the “factorial” mentioned in Material 2.

With this in mind, “$138 - 108 \div 6 = 5! = 1 \times 2 \times \cdots \times 5 = 120$” is clearly correct.

Problem Description

However, this problem may not be closely related to the background above.

We will give you $T$ test cases, and each test case contains a positive integer $n$.

For each test case, please help compute the number of integer triples $(x, y, z)$ that satisfy the following conditions:

1. $x \geq 0$, $z \geq 1$.
2. $x - y \div z = n!$ and $(x - y) \div z = \dfrac{n!}{n}$.

Since the answer may be very large, you need to output the result modulo $998244353$.

It is not hard to notice that the answer may be $\infty$. In that case, please handle it according to the “Output Format.”

Note that here it must satisfy $(x - y) \div z = \dfrac{n!}{n}$, not $= n$.

Also note that $\div$ here is not floor division. This clearly means you must ensure that $y \div z$ and $(x - y) \div z$ are integers.

Input Format

The input has $T + 1$ lines.

The first line contains an integer $T$.

The next $T$ lines each contain one integer $n$.

Output Format

Output $T$ lines, each being an integer or a string.

For the $i$-th line: if for the given $n$ on line $i + 1$ of the input, there are infinitely many integer triples $(x, y, z)$ satisfying $x - y \div z = n!$ and $(x - y) \div z = \dfrac{n!}{n}$, output inf. Otherwise, output the number of triples satisfying the conditions modulo $998244353$.

3
2
3
4

1
3
6

Hint

Explanation for Sample 1

The specific triples in the sample are as follows:

Constraints

For the first $20\%$ of the testdata, it is guaranteed that $T \leq 10$ and $n \leq 10$.

For the first $40\%$ of the testdata, it is guaranteed that $n \leq 10 ^ 3$.

For another $20\%$ of the testdata, it is guaranteed that $T = 1$.

For $100\%$ of the testdata, it is guaranteed that $1 \leq T \leq 10 ^ 5$ and $1 \leq n \leq 10 ^ 6$.

Translated by ChatGPT 5