定义贝尔数$B_n=\sum _{k=1}{n}S(n,k)$，其中$S(n,k)$为第二类斯特林数，我们有$B_{n+1}=\sum_{i=0}^{n}B_i*\tbinom{n}{i}$,
$\frac{B_{n+1}}{n!}=\sum_{i=1}^n\frac{1}{i!}*\frac{B_{n-i}}{(n-i)!}$
同乘 $x^n$
$\frac{B_{n+1}}{n!}x^n=\sum_{i=1}^n\frac{x^i}{i!}*\frac{B_{n-i}x^{n-i}}{(n-i)!}$
$\frac{d\frac{B{n+1}}{(n+1)!}x^{n+1}}{dx}=\sum_{i=1}^n\frac{xi}{i!}*\frac{B_{n-i}x^{n-i}}{(n-i)!}$
考虑指数型生成函数$F(x)=\sum_{x=0}^{\infty}\frac{B_i}{i!}$
有$\frac {dF}{dx}=e^x$,$ln|F|=e^x+C$,将$x=1$带入得$F=e^{e^x-1}$，这样这道题就做完了。
接下来是多项式EXP复习时间：
1. 多项式逆：考虑倍增，当前有$b(x)(mod x^{n})$，求 $B(x)(mod x^{2n})$，
注意到$0=(B(x)-b(x))^2*A(x) (mod x^{2n})$
整理有$B(x)=b(x)(2-A(x)) (mod x^{2n})$
2.多项式ln：注意到$\frac{d(ln(A(x))}{dx}=\frac{A'(x)}{A(x)}$
$ln(A(x))=\int \frac{A'(x)}{A(x)}dx$
3.多项式exp: 考虑牛顿迭代(下图by miskcoo)
我们关心$F(x)=e^{A(x)}$，带入易得$F(x)=F_0(x)(1-lnF_0(x)+A(x))(mod x^n)$
代码：
//#pragma GCC optimize(3,"Ofast","inline")
//#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define getchar nc
#define sight(c) ('0'<=c&&c<='9')
#define swap(a,b) a^=b,b^=a,a^=b
#define LL long long
#define debug(a) cout<<#a<<" is "<<a<<"\n"
#define dput(a) puts("a")
#define eho(x) for(int i=head[x];i;i=net[i])
#define fi first
#define se second
#define mo 998244353
inline char nc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
template <class T>
inline void read(T &x){// unsigned
static char c;
for (c=getchar();!sight(c);c=getchar());
for (x=0;sight(c);c=getchar())x=x*10+c-48;
}
template <class T> void write(T x){if (x<10) {putchar('0'+x); return;} write(x/10); putchar('0'+x%10);}
template <class T> inline void writeln(T x){ if (x<0) putchar('-'),x*=-1; write(x); putchar('\n'); }
template <class T> inline void writel(T x){ if (x<0) putchar('-'),x*=-1; write(x); putchar(' '); }
using namespace std;
LL qsm(LL x,LL y=mo-2){
static LL anw;
for (anw=1,x=x%mo;y;y>>=1,x=x*x%mo) if (y&1) anw=anw*x%mo;
return anw;
}
#define N 1000005
#define G 3
int rev[N];LL a[N],b[N];
void NTT(LL *a,int ln,int op){
int lim=1<<ln;
for (int i=0;i<lim;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<ln-1);
for (int i=0;i<lim;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
for (int i=1;i<lim;i<<=1) {
LL wn=qsm(G,(mo-1)/(i<<1));
if (op==-1) wn=qsm(wn);
for (int j=0;j<lim;j+=i<<1) {
LL w=1,X,Y;
for (int k=j;k<i+j;k++,w=w*wn%mo) {
X=a[k]; Y=w*a[k+i]%mo;
a[k]=(X+Y)%mo; a[k+i]=(X-Y+mo)%mo;
}
}
}
if (op==-1) {
LL sn=qsm(lim);
for (int i=0;i<lim;i++) a[i]=a[i]*sn%mo;
}
}
void mul(LL* a,LL *b,LL *c,int ln){//input array of len 1<<ln, return 1<<ln
static LL A[N],B[N];
int lim=(1<<ln);
for (int i=0;i<lim;i++) A[i]=a[i],B[i]=b[i];
for (int i=lim;i<2*lim;i++) A[i]=B[i]=0;
NTT(A,ln+1,1); NTT(B,ln+1,1);
for (int i=0;i<2*lim;i++)
c[i]=A[i]*B[i]%mo;
NTT(c,ln+1,-1);
}
void inv(LL *a,LL *b,int LG){
static LL C[N];
b[0]=qsm(a[0]);
for (int k=1;k<=LG;k++) {
mul(b,a,C,k);
for (int i=0;i<(1<<k);i++) C[i]=C[i]?mo-C[i]:0;
C[0]=(C[0]+2)%mo;
mul(C,b,b,k);
}
}
void Dif(LL *a,LL *b,int lim){ //传lim而不是LG
for (int i=0;i<lim;i++) b[i]=a[i+1]*(i+1)%mo;
b[lim-1]=0;
}
void Int(LL *a,LL *b,int lim){ //复杂度O(nlogn)
for (int i=lim-1;i;i--) b[i]=a[i-1]*qsm(i)%mo;
b[0]=0;
}
void Ln(LL *a,LL *b,int LG){
static LL C[N];
inv(a,b,LG);
Dif(a,C,1<<LG);
mul(b,C,b,LG);
Int(b,b,1<<LG);
}
void exp(LL *a,LL *b,int LG){
static LL D[N];
b[0]=1;
for (int k=1;k<=LG;k++) {
Ln(b,D,k);
for (int i=0;i<(1<<(k));i++) D[i]=(a[i]-D[i]+mo)%mo;
D[0]=(D[0]+1)%mo;
mul(b,D,b,k);
}
}
int n,T,X; LL fac[N];
signed main() {
#ifdef LOCAL
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
#endif
a[1]=1;
exp(a,b,17);
b[0]=0;
exp(b,a,17);
fac[0]=1; for (int i=1;i<N;i++) fac[i]=fac[i-1]*i%mo;
read(T);
while(T--) {
read(X); writeln(a[X]*fac[X]%mo);
}
return 0;
}
/*
3
1 3 3 1
1 3 3 1
*/