#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define pb push_back int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=1010,N=1000,MAXM=9000010,Mod=998244353; int n,m,k,ans,f[MAXN][2],g[MAXN][2]; void add(int &x,int y){x+=y;if(x>=Mod)x-=Mod;} int res[MAXN][MAXN]; bool vis[MAXN]; void sol(int m){ if(vis[m])return; vis[m]=1; k=N/m;ans=0; memset(f,0,sizeof(f)); for(int mn=m;mn<=N;mn++){ for(int i=mn;i<=N;i++)add(f[i][i==mn],1); } for(int i=0;i<=N;i++)add(res[m][i],f[i][1]); for(int i=2;i<=k;i++){ swap(f,g); for(int j=0;j<=N;j++){ for(int a=m;a+j<=N;a++){ add(f[a+j][0],g[j][0]*(a-m)%Mod); add(f[a+j][1],g[j][0]); add(f[a+j][1],g[j][1]*(a-m+1)%Mod); } g[j][0]=g[j][1]=0; } for(int i=0;i<=N;i++)add(res[m][i],f[i][1]); } for(int i=1;i<=N;i++)add(res[m][i],res[m][i-1]); } void slv(){ n=read(),m=read(); sol(m); printf("%lld\n",res[m][n]); } signed main(){ int _=read();while(_--) slv(); return 0; }