#include<bits/stdc++.h> #define enld endl #define int long long using namespace std; int n,m; const int mod=998244353; int qp(int x,int y){ int res=1; while(y){if(y&1)res*=x;x*=x;y>>=1;res%=mod;x%=mod;} return res; } int fac[100005],inv[100005]; void init(){ fac[0]=inv[0]=1; for(int i=1;i<=1e5;i++){ fac[i]=fac[i-1]*i%mod; inv[i]=inv[i-1]*qp(i,mod-2)%mod; } } int C(int x,int y){ return x<y?0:fac[x]*inv[y]%mod*inv[x-y]%mod; } void slv(){ cin>>n>>m; int ans=0; for(int i=1;i<=n;i++){ ans+=C(n-m*i+2*i,2*i)-C(n-m*i+i,2*i); ans%=mod; // cout<<ans<<endl; } cout<<(ans+mod)%mod<<endl; } signed main(){ init(); int T;cin>>T;while(T--) slv(); return 0; }