#include<bits/stdc++.h>
#include<immintrin.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#define FOR(i,a,b) for(int i=a,i##i=b;i<=i##i;++i)
#define ROF(i,a,b) for(int i=a,i##i=b;i>=i##i;--i)
typedef uint32_t u32;
typedef uint64_t u64;
using namespace std;
const int L=1e5,N=1.7e5+7,mod=998244353;
const double FK=(sqrt(5)+1)/2;
#define Load(ptr) (_mm256_loadu_si256((__m256i*)(ptr)))
#define Store(ptr, __A) _mm256_storeu_si256((__m256i*)(ptr), __A)
namespace Cirno_loves_Reimu{
	char buf[1<<20],obuf[1<<20],*p1,*p2,*p3=obuf;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
	#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
	inline int read(){
		int x=0;bool f=0;
		char c=getchar();
		while(!isdigit(c)&&c!='-')c=getchar();
		if(c=='-')f=1,c=getchar();
		while(isdigit(c))x=x*10+c-'0',c=getchar();
		return f?-x:x;
	}
	void write(u64 x){
		if(x<0)putchar('-'),x=-x;
		static char buf[15];
		static int len=-1;
		do buf[++len]=x%10+48,x/=10;while(x);
		while(len>=0)putchar(buf[len]),--len;
		putchar('\n');
	}
	#undef getchar
	#undef putchar
}using namespace Cirno_loves_Reimu;
inline u64 qpow(u64 a,u64 b){
	u64 R=1;
	for(;b;b>>=1,a=a*a%mod)if(b&1)R=R*a%mod;
	return R;
}
inline u32 to(u32 a){return (u32)((((u64)a)<<32)%998244353);}
inline u32 redc(u64 a){
	u32 b=(u32)a*998244351;
	u64 c=a+(u64)b*998244353;
	return (u32)(c>>32);
}
__attribute__((always_inline)) __m256i redc(__m256i a){
	__m256i b=_mm256_mul_epu32(a, _mm256_set1_epi32(998244351));
	__m256i c=_mm256_add_epi64(a, _mm256_mul_epu32(b, _mm256_set1_epi32(998244353)));
	return _mm256_srli_epi64(c,32);
}
int a[N];
u64 ans[N],f[N],num[N+1],I[]={to(1),to(1),to(1),to(1)};
void work(int i){
	int j=i;
	auto P=Load(I);
	u64 tmp[]={0,0,0,0};
	for(;j>3;j-=4){
		auto Y=redc(
			_mm256_add_epi64(
				_mm256_mul_epu32(
					Load(f+j-3),
					P
				),
				_mm256_mul_epu32(
					Load(f+j-4),
					Load(num+N-(a[i]-j+4))
				)
			)
		);
		Store(f+j-3,Y);
		Store(tmp,_mm256_add_epi64(Y,Load(tmp)));
	}
	FOR(k,0,3)ans[i]+=tmp[k];
	for(;j;--j){
		f[j]=redc(to(f[j])+f[j-1]*to(a[i]-j+1ll));
		ans[i]+=f[j];
	}
	ans[i]=redc(ans[i]+to(1));
}
signed main(){
	// freopen("dt.in","r",stdin);
	// freopen("dt.out","w",stdout);
	FOR(i,0,L)a[i]=(int)floor(FK*i);
	FOR(i,0,N)num[i]=to(N-i);
	f[0]=to(1);
	FOR(i,1,L)work(i);
	int T=read();
	while(T--)write(ans[read()]);
	fwrite(obuf,p3-obuf,1,stdout);
	return 0;
}