#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=300010,N=1000,MAXM=9000010,Mod=998244353; int n,m,k,ans,jc[MAXN],ny[MAXN]; int Pow(int x,int y){int rt=1;while(y){if(y&1)rt=rt*x%Mod;x=x*x%Mod,y>>=1;}return rt;} void add(int &x,int y){x+=y;if(x>=Mod)x-=Mod;} int C(int x,int y){return x<y?0:jc[x]*ny[x-y]%Mod*ny[y]%Mod;} void slv(){ n=read(),m=read();ans=0; for(int k=1;k*m<=n;k++)add(ans,(C(n-k*m+2*k,2*k)-C(n-k*m+k,2*k)+Mod)%Mod); printf("%lld\n",ans); } signed main(){ jc[0]=ny[0]=1;for(int i=1;i<=MAXN-5;i++)jc[i]=jc[i-1]*i%Mod,ny[i]=Pow(jc[i],Mod-2); int _=read();while(_--) slv(); return 0; }