#include<bits/stdc++.h> using namespace std; const int N=1e5+10,mod=998244353; int sz;int n,m; int fac[N*2],inv[N*2]; int LM=2e5+11; int qp(int a,int b){ int x=1; while(b){ if(b&1) x=1ll*a*x%mod; b>>=1;a=1ll*a*a%mod; }return x; } void init(){ fac[0]=1;for(int i=1;i<=LM;i++) fac[i]=1ll*fac[i-1]*i%mod; inv[LM]=qp(fac[LM],mod-2);for(int i=LM-1;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod; }int C(int u,int d){ //cout<<u<<' '<<d<<' '<<inv[1]<<endl; return 1ll*fac[d]*inv[u]%mod*inv[d-u]*(u<=d)%mod; } void slv(){ cin>>n>>m; int ans=0; for(int i=1;i*m<=n;i++){ ans+=(C(2*i,n-m*i+i+i)-C(2*i,n-m*i+i)+mod)%mod;ans%=mod; //cout<<ans<<' '; }cout<<ans<<endl; } int main(){ init();int t;cin>>t;while(t--) slv(); return 0; }