Counting Special Integer Triples

You are given T test cases. In each test case, you are given a positive integer n. For each test case, count the number of integer triples \((x,y,z)\) satisfying the following conditions:

1. \(x \ge 0\) and \(z \ge 1\). In addition, both \(y\div z\) and \((x-y)\div z\) must be integers (here \(\div\) denotes exact division, not floor division).
2. The following two equations hold:
   \(x - (y\div z) = n!\) and
   \((x-y)\div z = \dfrac{n!}{n}\).

Note: Since \(\dfrac{n!}{n} = (n-1)!\) for \(n\ge1\), the second equation actually is \((x-y)\div z = (n-1)!\). Also note that when \(n=1\), a special situation arises. For \(z=1\), the two equations reduce to \(x-y =1\) (since \(1! = 1\) and \(0! =1\)), and in this case \(y\) can be chosen arbitrarily, producing infinitely many solutions. In such cases, you should output infty (without quotes) instead of a number.

For \(n\ge2\), the equations force x and y to be determined in terms of an integer parameter \(k\) as follows. Since \(y\div z\) must be integer, let \(y = k\,z\). Then the first equation gives \(x = n!+k\) and the second equation becomes

[ \frac{(n!+k)-kz}{z} = (n-1)!,. ]

A short calculation shows that if we set (d=z-1) (with (d\ge1) since (z\ge2) for (n\ge2); note that for (n\ge2) the case (z=1) does not work), then the unique valid (k) is given by

[ k = \frac{(n-1)!,(n-z)}{z-1} = \frac{(n-1)!,( (n-1)-d)}{d},. ]

Thus for any (d\ge1) (where (d=z-1)) that makes (k) an integer, we obtain a valid triple ((x,y,z)) by taking (z=d+1,; y=k,z,; x=n!+k). To count the number of solutions for a given (n \ge 2), note that d must satisfy

[ d \mid (n-1)!,((n-1)-d),. ]

It turns out that the set of eligible (d) can be split into two parts:

1. For \(1 \le d \le n-1\): we require \(d \mid (n-1)!\,((n-1)-d)\).
2. For \(d > n-1\): since \((n-1)-d\) is negative, the divisibility condition is equivalent to \(d\) dividing \((n-1)!\,(n-1)\) (because \((n-1)!\,((n-1)-d) \equiv (n-1)!\,(n-1) \pmod{d}\)).

Your task is to compute the total number of valid triples modulo 998244353 for each test case. If the answer is infinite (which happens when \(n=1\)), output infty instead.

inputFormat

The first line contains an integer T (the number of test cases).

Each of the next T lines contains a single positive integer n.

outputFormat

For each test case, output a single line. If the number of valid triples is finite, print the number modulo 998244353. Otherwise (if there are infinitely many valid triples), print infty (without quotes).

sample

4
1
2
3
4

infty
1
3
6