#include using namespace std; #if __has_include() #include using namespace atcoder; templateistream &operator>>(istream &is,static_modint &a){long long b;is>>b;a=b;return is;} istream &operator>>(istream &is,modint &a){long long b;cin>>b;a=b;return is;} #endif #ifdef LOCAL #include "debug.h" #else #define debug(...) static_cast(0) #define debugg(...) static_cast(0) #define esper(...) static_cast(0) templateostream &operator<<(ostream &os,const pair&p){os<; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templateistream &operator>>(istream &is,pair&p){is>>p.first>>p.second;return is;} templateistream &operator>>(istream &is,vector &a){for(auto &i:a)is>>i;return is;} templatevoid operator++(pair&a,int n){a.first++,a.second++;} templatevoid operator--(pair&a,int n){a.first--,a.second--;} templatevoid operator++(vector&a,int n){for(auto &i:a)i++;} templatevoid operator--(vector&a,int n){for(auto &i:a)i--;} #define reps(i,a,n) for(int i=(a);i<(n);i++) #define rep(i,n) reps(i,0,n) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcountll(x) #define fin(x) return cout<(0) ll myceil(ll a,ll b){return (a+b-1)/b;} template auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id(d,init)); else return init; } void SOLVE(); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout<>testcase; for(int i=0;i struct ntt_root{ static constexpr int rank2=countr_zero(T::mod()-1); int g=primitive_root(T::mod()); arrayroot,invroot; arrayrate2,invrate2; arrayrate3,invrate3; ntt_root(){ root[rank2]=T::raw(g).pow((T::mod())>>rank2); invroot[rank2]=root[rank2].inv(); for(int i=rank2-1;i>=0;i--){ root[i]=root[i+1]*root[i+1]; invroot[i]=invroot[i+1]*invroot[i+1]; } { T prod=1,invprod=1; rep(i,rank2-1){ rate2[i]=root[i+2]*prod; invrate2[i]=invroot[i+2]*invprod; prod*=invroot[i+2]; invprod*=root[i+2]; } } { T prod=1,invprod=1; rep(i,rank2-2){ rate3[i]=root[i+3]*prod; invrate3[i]=invroot[i+3]*invprod; prod*=invroot[i+3]; invprod*=root[i+3]; } } } }; template void dft(vector&a){ int n=a.size(); static const ntt_root r; int h=countr_zero(n); ull mod2=(ull)T::mod()*T::mod(); int len=0; while(len void idft(vector&a){ int n=a.size(); static const ntt_root r; int h=countr_zero(n); ull mod2=(ull)T::mod()*T::mod(); int len=h; while(len){ if(len==1){ int p=1<<(h-1); T rot=1; rep(i,p){ T u=a[i],v=a[i+p]; a[i]=u+v; a[i+p]=(ull)(u.val()-v.val()+T::mod())*rot.val(); } len--; } else{ int p=1<<(h-len); T rot=1,imag=r.invroot[2]; rep(s,1<<(len-2)){ T rot2=rot*rot,rot3=rot*rot2; int of=s<<(h-len+2); rep(i,p){ ull a0=a[i+of].val(),a1=a[i+of+p].val(),a2=a[i+of+p*2].val(),a3=a[i+of+p*3].val(); ull k=T((T::mod()+a2-a3)*imag.val()).val(); a[i+of]=a0+a1+a2+a3; a[i+of+p]=(a0+T::mod()-a1+k)*rot.val(); a[i+of+p*2]=(a0+a1+T::mod()*2-a2-a3)*rot2.val(); a[i+of+p*3]=(a0+T::mod()*2-a1-k)*rot3.val(); } if(s+1!=1<<(len-2))rot*=r.invrate3[countr_zero(~(unsigned int)s)]; } len-=2; } } } template vectorntt_convolution(vector a,vector b){ int n=a.size(),m=b.size(),s=n+m-1; if(min(n,m)<60){ vectorret(s,0); if(nc(z); rep(i,z)c[i]=a[i]*b[i]; idft(c); T g=T::raw(z).inv(); rep(i,s)c[i]*=g; return {c.begin(),c.begin()+s}; } template vector fps_inv(const vector &a,int deg=-1){ int n=a.size(); if(deg==-1)deg=n; assert(a[0]!=T(0)); vector ret(deg); ret[0]=a[0].inv(); for(int m=1;m f(a.begin(),a.begin()+min(n,m*2)); if(f.size() g(ret); f.resize(m*2); dft(f); g.resize(m*2); dft(g); rep(i,m*2)f[i]*=g[i]; idft(f); T inv=T::raw(m*2).inv(); rep(i,m)f[i]=0; reps(i,m,m*2)f[i]*=inv; dft(f); rep(i,m*2)f[i]*=g[i]; idft(f); rep(i,m*2)f[i]*=inv; reps(i,m,min(deg,m*2))ret[i]-=f[i]; } return ret; } template vector fps_diff(const vector&a){ int n=a.size(); vectorb(max(0,n-1)); reps(i,1,n)b[i-1]=a[i]*i; return b; } template vector fps_integral(const vector&a){ int n=a.size(); vectorb(n+1); b[0]=0; if(n)b[1]=1; reps(i,2,n+1)b[i]=-b[T::mod()%i]*(T::mod()/i); rep(i,n)b[i+1]*=a[i]; return b; } template vector fps_log(const vector&a,int deg=-1){ int n=a.size(); if(deg==-1)deg=n; vectorb=fps_integral(ntt_convolution(fps_diff(a),fps_inv(a,deg))); return {b.begin(),b.begin()+deg}; } template vector fps_exp(const vector&a,int deg=-1){ assert(a.empty()||a[0]==0); int n=a.size(); if(deg==-1)deg=n; vectorb{1}; for(int m=1;mnxt=fps_log(b,m*2); rep(i,m*2)nxt[i]*=-1; rep(i,min(n,m*2))nxt[i]+=a[i]; nxt[0]++; b=ntt_convolution(b,nxt); b.resize(m*2); } return {b.begin(),b.begin()+deg}; } template vector fps_pow(vector a,ll k,int deg=-1){ int n=a.size(); if(deg==-1)deg=n; if(k==0){ vectorret(deg,0); ret[0]=1; return ret; } int of=0; while(a[of]==0&&of!=n)of++; if(of==n)return vector(deg,0); if(of!=0&&k>=deg)return vector(deg,0); if(of*k>=deg)return vector(deg,0); a.erase(a.begin(),a.begin()+of); n=a.size(); T a0=a[0]; T inv=a[0].inv(); rep(i,n)a[i]*=inv; vectorlg=fps_log(a,deg); rep(i,deg)lg[i]*=k; vectorep=fps_exp(lg,deg); T pw=a0.pow(k); rep(i,deg)ep[i]*=pw; vectorret(deg,0); reps(i,of*k,deg)ret[i]=ep[i-of*k]; return ret; } template vector fps_pow_sparse(const vector&a,ll k,int deg=-1){ int n=a.size(); if(deg==-1)deg=n; vector>b; rep(i,n)if(a[i]!=0)b.emplace_back(i,a[i]); if(b.empty()){ vectorret(deg,0); if(k==0)ret[0]=1; return ret; } int of=b[0].first; T b0=b[0].second,inv=b0.inv(); for(auto &i:b){ i.first-=of; i.second*=inv; } b0=b0.pow(k); vectorret(deg,0); ret[0]=1; rep(i,deg-1){ T cu=0; for(auto [j,c]:b){ if(i-j+1<0)continue; if(j==0)continue; cu-=c*ret[i-j+1]*(i-j+1); cu+=ret[i-j+1]*k*j*c; } ret[i+1]=cu/(i+1); } if(of){ if(k>=deg||of*k>=deg)ret.assign(deg,0); else{ ret.insert(ret.begin(),of*k,0); ret.resize(deg); } } for(auto &i:ret)i*=b0; return ret; } template vector fps_div_sparse(vector a,const vector&b,int deg=-1){ int n=a.size(),m=b.size(); if(deg==-1)deg=n; a.resize(deg,0); assert(b[0]!=0); vector>c; reps(i,1,m)if(b[i]!=0)c.emplace_back(i,b[i]); T v=b[0].inv(); rep(i,deg){ for(auto [j,e]:c){ if(j>i)break; a[i]-=a[i-j]*e; } a[i]*=v; } return a; } template inline vector fps_inv_sparse(const vector&a,int deg=-1){ return fps_div_sparse({1},a,(deg==-1?a.size():deg)); } template vectorfps_fode_sparse(const vector&a,const vector&b){ assert(a.size()==b.size()); assert(a[0]==1); int n=a.size(); vector>c,d; reps(i,1,n)if(a[i]!=0)c.emplace_back(i,a[i]); rep(i,n)if(b[i]!=0)d.emplace_back(i,b[i]); vectorf(n),df(n-1); f[0]=1; vectorinv(n); rep(i,n-1){ T v=0; for(auto [j,x]:c){ if(j>i)break; v+=x*df[i-j]; } for(auto [j,x]:d){ if(j>i)break; v+=x*f[i-j]; } df[i]=-v; if(i==0)inv[1]=1; else inv[i+1]=-inv[T::mod()%(i+1)]*(T::mod()/(i+1)); f[i+1]=df[i]*inv[i+1]; } return f; } template vector fps_pow_sparse(const vector&a,const vector&b,ll k,ll l,int deg=-1){ int n=a.size(),m=b.size(); if(deg==-1)deg=n; assert(a[0]==1); vector>c,d; rep(i,n)if(a[i]!=0)c.emplace_back(i,a[i]); rep(i,m)if(b[i]!=0)d.emplace_back(i,b[i]); vectorf(deg,0),g(deg,0); for(auto [i,x]:c){ for(auto [j,y]:d){ if(i+j>=deg+1)continue; T z=x*y; if(i+j T bostan_mori(vector p,vector q,ll k){ int z=1; int n=p.size(),m=q.size(); while(zv(z/2); rep(i,z/2)v[i]=q[i*2]*q[i*2+1]; idft(p),idft(v); T inv=T::raw(z).inv(),inv2=inv*2; rep(i,z/2)v[i]*=inv2; vectoru(n); if(k&1)rep(i,n)u[i]=p[i*2+1]*inv; else rep(i,n)u[i]=p[i*2]*inv; u.resize(z,0),v.resize(z,0); swap(p,u),swap(q,v); k>>=1; } return p[0]; } template vector berlekamp_massey(const vector&s){ const int n=s.size(); vectorb,c; b.reserve(n+1),c.reserve(n+1); b.emplace_back(1),c.emplace_back(1); T y=1; reps(i,1,n+1){ int l=c.size(),m=b.size(); T x=0; rep(j,l)x+=c[j]*s[i-l+j]; b.emplace_back(0); ++m; if(x==0)continue; T f=x/y; if(l T kth_term(vectorp,ll k){ vectorq=berlekamp_massey(p); if(T::mod()==998244353){ p=ntt_convolution(p,q); p.resize(q.size()-1); return bostan_mori(p,q,k); } auto convolution_naive=[](vector&x,const vector&y)->void { vectortemp(x.size()+y.size()-1,0); rep(i,x.size())rep(j,y.size())temp[i+j]+=x[i]*y[j]; swap(x,temp); }; convolution_naive(p,q); int n=q.size(); p.resize(n-1); vectormq(n); while(k){ rep(i,n)mq[i]=q[i]*(i&1?-1:1); convolution_naive(p,mq); convolution_naive(q,mq); vectoru(n-1),v(n); if(k&1)rep(i,n-1)u[i]=p[i*2+1]; else rep(i,n-1)u[i]=p[i*2]; rep(i,n)v[i]=q[i*2]; swap(p,u),swap(q,v); k>>=1; } if(p.empty())return 0; else return p[0]; } template vectorfps_polynominal_talor_shift(vectora,T c,int deg=-1){ if(deg==-1)deg=a.size(); else if(degfact(deg),factinv(deg),inv(deg); fact[0]=fact[1]=factinv[0]=factinv[1]=inv[1]=1; reps(i,2,deg){ fact[i]=fact[i-1]*i; inv[i]=-inv[T::mod()%i]*(T::mod()/i); factinv[i]=factinv[i-1]*inv[i]; } vectorf(deg,0),g(deg,0); T now=1; rep(i,a.size()){ f[i]=a[i]*fact[i]; g[deg-i-1]=now*factinv[i]; now*=c; } f=ntt_convolution(f,g); vectorret(deg); rep(i,deg)ret[i]=f[i+deg-1]*factinv[i]; return ret; } template vectorfps_middle_product(vectora,vectorb){ assert(a.size()>=b.size()); reverse(all(b)); int n=a.size(),m=b.size(); int z=1; while(z(a.begin()+m-1,a.begin()+n); } template vector>convolution2d(vector>a,vector>b){ int x=a.size()+b.size()-1,y=a[0].size()+b[0].size()-1; vectorf(a.size()*y),g(b.size()*y); rep(i,a.size())rep(j,a[i].size())f[i*y+j]=a[i][j]; rep(i,b.size())rep(j,b[i].size())g[i*y+j]=b[i][j]; auto c=ntt_convolution(f,g); vector>ret(x,vector(y)); rep(i,x)rep(j,y)ret[i][j]=c[i*y+j]; return ret; } template vectorfps_pows(vectorf,vectorg,int n){ int sz=f.size(); vector>p(sz,vector(2)),q(sz,vector(2)); q[0][0]=1; rep(i,min(g.size(),sz))p[i][0]=g[i]; rep(i,sz)q[i][1]=-f[i]; int k=sz-1; while(k){ int x=p.size(),y=p[0].size(); vector>mq(q); for(int i=1;i>f=convolution2d(p,mq); vector>g=convolution2d(q,mq); p.resize(k/2+1); q.resize(k/2+1); if(k&1)rep(i,p.size())p[i]=f[i*2+1]; else rep(i,p.size())p[i]=f[i*2]; rep(i,q.size())q[i]=g[i*2]; rep(i,p.size())if(p[i].size()>n+1)p[i].resize(n+1); rep(i,q.size())if(q[i].size()>n+1)q[i].resize(n+1); k>>=1; } vectorf2(p[0]),g2(q[0]); vectorret=ntt_convolution(f2,fps_inv(g2)); ret.resize(n+1); return ret; } template vectorfps_composition(vectorf,vectorg,int deg=-1){ if(deg==-1)deg=f.size(); f.resize(deg,0),g.resize(deg,0); T c=g[0]; g[0]=0; f=fps_polynominal_talor_shift(f,c); auto dfs=[&](auto self,vector>p)->vector> { int h=p.size(),w=p[0].size(); if(h==1){ vector>ret(h,vector(w)); rep(i,f.size())ret[0][i]=f[i]; return ret; } vector>p2(p); rep(i,h)if(i&1)rep(j,w)p2[i][j]=-p2[i][j]; vector>p3=convolution2d(p,p2); int h2=(h+1)/2; rep(i,h2)p3[i]=p3[i*2]; p3.resize(h2); vector>q=self(self,p3); vectora(2*h*(2*w-1)-1); rep(i,q.size())rep(j,q[i].size()){ a[(i*2+!(h&1))*(w*2-1)+j]=q[i][j]; } vectorb(2*h*(2*w-1)); rep(i,h)rep(j,w){ b[i*(2*w-1)+j]=p2[i][j]; } reverse(all(b)); a=ntt_convolution(a,b); a.erase(a.begin(),a.begin()+b.size()-1); a.resize(h*(2*w-1)); vector>ret(h,vector(w)); rep(i,h)rep(j,w){ ret[i][j]=a[i*(2*w-1)+j]; } return ret; }; vector>g2(deg,vector(2,0)); g2[0][0]=1; rep(i,deg)g2[i][1]=-g[i]; auto p=dfs(dfs,g2); vectorret(deg); rep(i,deg)ret[i]=p[i][0]; reverse(all(ret)); return ret; } using mint=modint998244353; void SOLVE(){ int n,k; cin>>n>>k; vectorf(n+1,0),g(n+1,0); reps(i,1,n+1){ if(ll(i)*(k+1)<=n)for(int j=1;;j++){ int d=i*j*(k+1); if(d>n)break; f[d]-=mint(j).inv(); } for(int j=1;;j++){ int d=i*j; if(d>n)break; g[d]-=mint(j).inv(); } } f=fps_exp(f),g=fps_exp(g); f=ntt_convolution(f,fps_inv(g)); reps(i,1,n+1)cout<