這道題可不入門。

$\text{[Problem?Discription]}$

給定 $n$，求有多少組 $(x,y,z)$ 滿足：

1. $x?\frac{y}{z}=n!$
2. $\frac{x?y}{z}=\frac{n!}{n}$

其中 $n!$ 表示 $n$ 的階乘，即 $\prod _{i=1}^{n}i$。$x,y,z$ 為整數，可以是負整數。

多組詢問。$1\le T\le 1\times 10^5,1\le n\le 1\times 10^6$。

$\text{[Analysis]}$

作為一個經歷了高考摧殘的人，最會干的事情就是化簡冗長的式子。

干瞪眼看不出這兩個式子有什么規律，變量太多了，因此考慮先消元。

由 $x?\frac{y}{z}=n!$ 得 $x=\frac{y}{z}+n!$，把它帶入第二個式子中可得：

$$\begin{array}{rl}\frac{x?y}{z}& =\frac{\frac{y}{z}+n!?y}{z}\\ & =\frac{y+zn!?zy}{z^2}\\ & =\frac{n!}{n}\end{array}$$

通分，

$$\begin{array}{rl}ny?nzn!?nzy& =n!z^2\\ n(z?1)y& =n!z(n?z)\\ y& =\frac{(n?1)!z(n?z)}{z?1}\end{array}$$

因此，滿足題意的 $(z?1)$ 一定是 $(n?1)!z(n?z)$ 的因數。除了 $z=2$ 外，$(z?1)$ 不會是 $z$ 的因數，且 $\gcd (z?1,z)=1$，因此 $(z?1)$ 為 $(n?1)!(n?z)$ 的因數。然而這個式子上下都含有 $z$，愚蠢的人腦是分析不出什么東西來的。

考慮引入新的參數 $k$。

$$\begin{array}{rl}(n?1)!(n?z)& =k(z?1)\\ n!?(n?1)!z& =kz?k\\ \left[(n?1)!+k\right]z& =n!+k\\ z& =\frac{n!+k}{(n?1)!+k}\end{array}$$

實話實說，這是一個非常美的式子，可惜它和上面一樣，上下都含有 $k$，因此從難度上并沒有變化。

思路貌似到這里就斷了，怎么辦？當然是看題解去（bushi）。

上面是把消去了 $x$ 保留 $y$，行不通的時候當然試試消去 $y$ 留下 $x$ 啦。

也不用重新計算，只需要把 $y$ 用 $z$ 表達的那個式子帶入 $x$ 中，就可以得到：

$$x=\frac{y}{z}+n!=\frac{(n?1)(n?1)!z}{z?1}$$

同樣，$z\ne 2$ 時，$(z?1)$ 不是 $z$ 的因數，因此 $(z?1)$ 一定是 $(n?1)(n?1)!$ 的因數。$z=2$ 時，$z?1=1$ 當然也是 $(n?1)(n?1)!$ 的因數。

因此問題轉化為求 $(n?1)(n?1)!$ 的因數的個數。這個問題和原問題是等價的。記答案為 $\text{ans}(n)$。

為什么？

考慮 $(n?1)(n?1)!$ 的一個因數 $z$，帶入上式就一定可以唯一的算出一個 $x(z),y(z)$，$x(z)$ 必然是一個整數。而 $y=z(x?n!)$（由最開始的式子變形而來）在 $x,z$ 都是整數的情況下當然是整數。因此一個 $z$ 就唯一確定一組 $(x,y,z)$，而不同的 $z$ 確定的當然是不同的 $(x,y,z)$。兩個問題的解構成一一映射。

根據因數個數定理，我們需要求的就是 $(n?1)(n?1)!$ 不同質因數出現的次數。

設每個質因數出現的次數為 $f(p_i)$。答案即為 $\prod _{i=1}^{\text{prime?count}}\left(1+f(p_i)\right)$。

不能每次都重新求，考慮怎么從 $\text{ans}(n?1)$ 遞推得到 $\text{ans}(n)$。

我們可以快速的將 $n$ 和 $(n?1)$ 分解質因數，然后 $f(p_i)$ 減去 $(n?1)$ 的質因數出現次數，加上兩倍的 $n$ 的質因數個數就行了（因為階乘和階乘前各有一個 $n$，所以是兩倍）。

但是根號級別的分解質因數還是太慢了，能不能降低時間復雜度呢？

答案是可以的。如果我們知道 $n$ 的質因數都有誰，就不用一個一個數去實驗了。當然不能把所有質因數都記下來（都記下來了還要試除法干嘛了），但是通過線性篩，我們可以順便得到每個數的最小質因數是多少。每次除以最小質因數就可以大大加快算法了。

配合線性求逆元，程序跑得飛快。

還漏了一個問題，在上面那個式子中，$(z?1)$ 是作為分母的，因此 $z\ne 1$。有沒有 $z=1$ 的情況呢？

$z=1$ 時有 $x?y=n!=\frac{n!}{n}$，因此 $n=1$。因此只有 $n=1$ 時答案為無窮。

$\text{Code}$

int f[N],n,T,ans[N];int prime[N],prcnt;
bool is_prime[N];
int minn_prime[N];
void get_prime(int n){for(int i=2;i<=n;i++)is_prime[i]=true;for(int i=2;i<=n;i++){if (is_prime[i]){minn_prime[i]=i;prime[++prcnt]=i;}for(int j=1;j<=prcnt;j++){if (1ll*i*prime[j]>n) break;is_prime[i*prime[j]]=false;minn_prime[i*prime[j]]=prime[j];if (i%prime[j]==0) break;}}
}int ksm(int a,int b){自己寫快速冪
}int inv[N],fac[N];void init_inv(int n){fac[0]=1;for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;int tmp=ksm(fac[n],mod-2);inv[n]=1ll*fac[n-1]*tmp%mod;for(int i=n-1;i>=1;i--){tmp=1ll*tmp*(i+1)%mod;inv[i]=1ll*tmp*fac[i-1]%mod;}
}vector<pair<int,int> > prdiv;
void dp_init(int n){int cur=1;ans[0]=1;for(int i=1;i<=n;i++){prdiv.clear();int tmp=i;while (tmp!=1){int cnt=0,div=minn_prime[tmp];while (tmp%div==0){tmp/=div;cnt++;}prdiv.push_back(make_pair(div,cnt));}tmp=prdiv.size();for(int j=0;j<tmp;j++){int val=prdiv[j].first,cnt=prdiv[j].second;cur=1ll*cur*inv[1+f[val]]%mod;f[val]+=(cnt<<1);cur=1ll*cur*(1+f[val])%mod;}ans[i]=cur;for(int j=0;j<tmp;j++){int val=prdiv[j].first,cnt=prdiv[j].second;cur=1ll*cur*inv[1+f[val]]%mod;f[val]-=cnt;cur=1ll*cur*(1+f[val])%mod;}}
}int main(){get_prime(1e6);init_inv(1e6);dp_init(1e6);T=read();for(int Case=1;Case<=T;Case++){n=read();if (n==1) printf("inf\n");else printf("%d\n",ans[n-1]);}return 0;
}