题目传送门
分析：
跑去写了一下烷基计数（博客），这道题要先会求烷基的生成函数
我们假设求出来了烷基的生成函数为(A)
（蒟蒻表示被开除人籍了，看不大懂）
反正先照着式子写一下吧
（省选不退役再回来补吧2333）
upd：
退役失败，回来补坑
以下为口胡。。。
P函数是确定一个重心，四面接烷基的方案，使用Ploya定理去重
Q函数是去除沿某一条边为对称轴翻转同构，把那条边断开挤一个点在里面
S函数是P-Q里面多减去的两个重心的方案，需要加回来
（不太明白，这种神仙题考场上也写不出来的2333）
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 2000005
#define MOD 998244353
using namespace std;
inline int getint()
{
int num=0,flag=1;char c;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
while(c>='0'&&c<='9')num=num*10+c-48,c=getchar();
return num*flag;
}
int N=100000;
int F[maxn],F2[maxn],F3[maxn],F4[maxn],rev[maxn];
int ans[maxn];
int Wl,Wl2,w[maxn];
inline int ksm(int num,int k)
{
int ret=1;
for(;k;k>>=1,num=1ll*num*num%MOD)if(k&1)ret=1ll*ret*num%MOD;
return ret;
}
void init(int len)
{
Wl=w[0]=1;
while((Wl<<1)<=len)Wl<<=1;
w[1]=ksm(3,(MOD-1)/(Wl<<1)),Wl2=Wl<<1;
for(int i=2;i<=Wl2;i++)w[i]=1ll*w[i-1]*w[1]%MOD;
}
inline int upd(int x){return x<MOD?x:x-MOD;}
inline void getrev(int len)
{for(int i=0;i<len;i++)rev[i]=(rev[i>>1]>>1)|(i&1?len>>1:0);}
inline void NTT(int *A,int len,int opt)
{
for(int i=0;i<len;i++)if(i<rev[i])swap(A[i],A[rev[i]]);
for(int i=1,B=Wl;i<len;i<<=1,B>>=1)
{
for(int j=0,t=i<<1;j<len;j+=t)for(int k=0,x=0;k<i;k++,x+=B)
{
int v=1ll*A[i+j+k]*w[opt==1?x:Wl2-x]%MOD;
A[i+j+k]=upd(A[j+k]-v+MOD),A[j+k]=upd(A[j+k]+v);
}
}
if(!~opt)for(int i=0,Inv=ksm(len,MOD-2);i<len;i++)A[i]=1ll*A[i]*Inv%MOD;
}
inline void getinv(int *A,int *B,int n)
{
static int T[maxn];
for(int i=0;i<(n<<1);i++)B[i]=0;
B[0]=ksm(A[0],MOD-2);
for(int len=2;len<=n;len<<=1)
{
for(int i=0;i<len;i++)T[i]=A[i],T[i+len]=0;
getrev(len<<1);
NTT(T,len<<1,1),NTT(B,len<<1,1);
for(int i=0;i<(len<<1);i++)B[i]=1ll*B[i]*upd(2-1ll*T[i]*B[i]%MOD+MOD)%MOD;
NTT(B,len<<1,-1);
for(int i=len;i<(len<<1);i++)B[i]=0;
}
}
inline void solve(int n)
{
static int G[maxn],H[maxn],S[maxn],C[maxn],T[maxn];
F[0]=1;
for(int i=2;i<=n;i<<=1)
{
for(int j=0;j<i;j++)T[j]=F[j],S[j]=C[j]=T[j+i]=S[j+i]=C[j+i]=0;
for(int j=0;j<i;j+=2)S[j]=F[j/2];
for(int j=0;j<i;j+=3)C[j]=F[j/3];
getrev(i<<1);
NTT(T,i<<1,1),NTT(S,i<<1,1);
for(int j=0;j<(i<<1);j++)G[j]=1ll*T[j]*(1ll*T[j]*T[j]%MOD+3ll*S[j])%MOD,H[j]=3*(1ll*T[j]*T[j]+S[j])%MOD;
NTT(G,i<<1,-1),NTT(H,i<<1,-1);
for(int j=i;j<(i<<1);j++)G[j]=H[j]=0;
for(int j=i-1;j;j--)G[j]=((1ll*G[j-1]+2ll*C[j-1]-6ll*F[j])%MOD+MOD)%MOD,H[j]=H[j-1];
G[0]=0,H[0]=MOD-6;
NTT(G,i<<1,1),getinv(H,T,i),NTT(T,i<<1,1);
for(int j=0;j<(i<<1);j++)G[j]=1ll*G[j]*T[j]%MOD;
NTT(G,i<<1,-1);
for(int j=0;j<i;j++)F[j]=(F[j]-G[j]+MOD)%MOD;
}
}
inline void work(int len)
{
static int A1[maxn],A2[maxn],A3[maxn],A4[maxn],T[maxn];
for(int i=0;i*4<len;i++)ans[i*4+1]=1ll*ksm(4,MOD-2)*F[i]%MOD;
for(int i=0;i*2<len;i++)ans[i*2]=F[i];
getrev(len);
NTT(F,len,1),NTT(F2,len,1),NTT(F3,len,1),NTT(F4,len,1);
for(int i=0;i<len;i++)
{
A1[i]=1ll*F[i]*F[i]%MOD*F[i]%MOD*F[i]%MOD;
A2[i]=3ll*F2[i]*F2[i]%MOD;
A3[i]=6ll*F[i]*F[i]%MOD*F2[i]%MOD;
A4[i]=8ll*F[i]*F3[i]%MOD;
T[i]=(1ll*A1[i]+A2[i]+A3[i]+A4[i])*ksm(24,MOD-2)%MOD;
}
NTT(T,len,-1);
for(int i=0;i<len;i++)ans[i+1]=(ans[i+1]+T[i])%MOD;
for(int i=0;i<len;i++)T[i]=(1ll*F[i]*F[i]%MOD*ksm(2,MOD-2)+1ll*F2[i]*ksm(2,MOD-2)-F[i])%MOD;
NTT(T,len,-1);
for(int i=0;i<len;i++)ans[i]=upd(ans[i]-T[i]+MOD);
}
int main()
{
int len=1;
while(len<=4*N)len<<=1;
init(len);
solve(len>>2);
for(int i=0;i<len;i++)F2[i]=i%2?0:F[i/2];
for(int i=0;i<len;i++)F3[i]=i%3?0:F[i/3];
for(int i=0;i<len;i++)F4[i]=i%4?0:F[i/4];
work(len);
int T=getint();
while(T--)
{
int n=getint();
printf("%d
",ans[n]);
}
}
