#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#define N 100000
#define K 18
#define M 262144
#define g 3
#define mod 998244353
using namespace std;
const double eps=1e-8;
double ds=(sqrt(5)+1)/2;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int fast_pow(int a,int b)
{
	int res=1,mul=a;
	while (b)
	{
		if (b&1) res=1ll*res*mul%mod;
		mul=1ll*mul*mul%mod,b>>=1;
	}
	return res;
}
int MD(int x)
{
	return x>=mod?x-mod:x;
}
int MD2(int x)
{
	return x<0?x+mod:x;
}
void Adder(int &x,int d)
{
	x+=d;
	if (x>=mod) x-=mod;
	return;
}
void Adder2(int &x,int d)
{
	x+=d;
	if (x<0) x+=mod;
	return;
}
int ST,n,length,F[N+1],fac[N+1],invfac[N+1],inv[N+1],tB[N+1],a[N+1],A[M+1],B[M+1],num[M+1],rev[M+1],wn[K+1][M+1],wn2[K+1][M+1];
void NTT(int limit,int *s,int type)
{
	int s1,s2;
	for (int i=1;i<limit;++i) rev[i]=(rev[i>>1]>>1)|((i&1)?(limit>>1):0);
	for (int i=1;i<limit;++i)
		if (rev[i]>i)
			swap(s[i],s[rev[i]]);
	if (type==1)
	{
		for (int i=2;i<=limit;i<<=1)
			for (int j=0;j+i-1<limit;j+=i)
				for (int k=j;k<j+(i>>1);++k)
					s1=s[k],s2=1ll*s[k+(i>>1)]*wn[num[i]][k-j]%mod,s[k]=MD(s1+s2),s[k+(i>>1)]=MD2(s1-s2);
	}
	else
	{
		for (int i=2;i<=limit;i<<=1)
			for (int j=0;j+i-1<limit;j+=i)
				for (int k=j;k<j+(i>>1);++k)
					s1=s[k],s2=1ll*s[k+(i>>1)]*wn2[num[i]][k-j]%mod,s[k]=MD(s1+s2),s[k+(i>>1)]=MD2(s1-s2);
		s1=fast_pow(limit,mod-2);
		for (int i=0;i<=limit;++i) s[i]=1ll*s[i]*s1%mod;
	}
	return;
}
vector<int>operator * (vector<int>a,vector<int>b)
{
	int limit=1;
	vector<int>c(a.size()+b.size()-1);
	while (limit<=a.size()+b.size()) limit<<=1;
	for (int i=0;i<=limit;++i) A[i]=B[i]=0;
	for (int i=0;i<a.size();++i) A[i]=a[i];
	for (int i=0;i<b.size();++i) B[i]=b[i];
	NTT(limit,A,1),NTT(limit,B,1);
	for (int i=0;i<=limit;++i) A[i]=1ll*A[i]*B[i]%mod;
	NTT(limit,A,-1);
	for (int i=0;i<c.size();++i) c[i]=A[i];
	return c;
}
struct seg
{
	struct node
	{
		vector<int>data;
	};
	node tree[(N<<2)+1];
	void push_up(int k)
	{
		tree[k].data=tree[k<<1].data*tree[k<<1|1].data;
		return;
	}
	void build(int k,int l,int r)
	{
		if (l==r)
		{
			tree[k].data={a[l],1};
			return;
		}
		int mid=(l+r)>>1;
		build(k<<1,l,mid),build(k<<1|1,mid+1,r),push_up(k);
		return;
	}
	void solve(int k,int l,int r,vector<int>p)
	{
		if (l==r)
		{
			F[l]=MD(1ll*p[0]*a[l]%mod+p[1]);
			return;
		}
		int mid=(l+r)>>1,limit=1;
		vector<int>p1(mid-l+2);
		vector<int>p2(r-mid+1);
		for (int i=0;i<=mid-l+1;++i) p1[i]=p[i];
		while (limit<=r-l+1) limit<<=1;
		for (int i=0;i<=limit;++i) A[i]=B[i]=0;
		for (int i=0;i<=r-l+1;++i) A[i]=p[i];
		for (int i=0;i<=mid-l+1;++i) B[mid-l+1-i]=tree[k<<1].data[i];
		NTT(limit,A,1),NTT(limit,B,1);
		for (int i=0;i<=limit;++i) A[i]=1ll*A[i]*B[i]%mod;
		NTT(limit,A,-1);
		for (int i=0;i<=r-mid;++i) p2[i]=A[mid-l+1+i];
		solve(k<<1,l,mid,p1),solve(k<<1|1,mid+1,r,p2);
		return;
	}
};
seg T;
void solve(int l,int r)
{
	if (l==r)
	{
		if (l) tB[l]=1ll*tB[l]*inv[l]%mod;
		return;
	}
	int mid=(l+r)>>1,limit=1;
	solve(l,mid);
	while (limit<=r-l) limit<<=1;
	for (int i=0;i<=limit;++i) A[i]=B[i]=0;
	for (int i=l;i<=mid;++i) A[i-l]=tB[i];
	for (int i=1;i<=r-l;++i) B[i]=invfac[i-1];
	NTT(limit,A,1),NTT(limit,B,1);
	for (int i=0;i<=limit;++i) A[i]=1ll*A[i]*B[i]%mod;
	NTT(limit,A,-1);
	for (int i=mid+1;i<=r;++i) Adder(tB[i],A[i-l]);
	solve(mid+1,r);
	return;
}
int main()
{
	vector<int>p;
	fac[0]=1;
	for (int i=1;i<=N;++i) fac[i]=1ll*fac[i-1]*i%mod;
	invfac[N]=fast_pow(fac[N],mod-2);
	for (int i=N-1;i>=0;--i) invfac[i]=1ll*invfac[i+1]*(i+1)%mod;
	for (int i=1;i<=N;++i) inv[i]=1ll*fac[i-1]*invfac[i]%mod;
	for (int i=2,w;i<=M;i<<=1)
	{
		num[i]=++length,w=fast_pow(g,(mod-1)/i);
		for (int j=0,res=1;j<(i>>1);++j,res=1ll*res*w%mod) wn[num[i]][j]=res;
		w=fast_pow(g,(mod-1)/i*(i-1));
		for (int j=0,res=1;j<(i>>1);++j,res=1ll*res*w%mod) wn2[num[i]][j]=res;
	}
	tB[0]=1,solve(0,N);
	for (int i=0;i<=N;++i) tB[i]=1ll*tB[i]*fac[i]%mod;
	p.resize(N+1);
	for (int i=0;i<=N;++i) p[i]=tB[i];
	for (int i=1;i<=N;++i) a[i]=floor(ds*i-eps)-i+1;
	T.build(1,1,N),T.solve(1,1,N,p),ST=read();
	while (ST--) n=read(),printf("%d\n",F[n]);
	return 0;
}