#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=1e6+10,mod=998244353; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,jc[maxn],jc_inv[maxn]; int qp(int a,int b){ int res=1; while(b){ if(b&1)res=res*1ll*a%mod; a=a*1ll*a%mod;b>>=1; }return res; } void init(){ jc[0]=jc_inv[0]=1; up(i,1,int(2e5))jc[i]=jc[i-1]*1ll*i%mod,jc_inv[i]=qp(jc[i],mod-2); } int C(ll n,ll m){if(m<0||n<0||m<n)return 0;return jc[m]*1ll*jc_inv[m-n]%mod*1ll*jc_inv[n]%mod;} int ball(ll n,ll m){return C(n-1,n+m-1);} void slv(){ n=read(),m=read();int res=0; up(k,1,n){ ll rem=n-1ll*k*m; int f1=ball(2*k+1,rem); int f2=ball(2*k+1,rem-k); (res+=f1)%=mod,res=(res-f2+mod)%mod; } printf("%d\n",res); } int main(){ //freopen("magic.in","r",stdin); //freopen("magic.out","w",stdout); init();int t=read();while(t--)slv(); fclose(stdin); fclose(stdout); return 0; } //100pts