int n,k;
int B[N]={1,1,2};
int main() {
int t;
sf(t);
for(int i=3;i<N;++i)
for(int j=1,f=1;f;++j)
for(int k=-1;k<2;k+=2){
int w=(3*j*j+k*j)/2;
if(w>i){f=0;break;}
if(j%2)B[i]=(B[i]+B[i-w])%mod;
else B[i]=(B[i]-B[i-w]+mod)%mod;
}
while(t--){
sf(n);sf(k);
int ans=0;
ans=B[n]%mod;
for(int i=1,f=1;f;++i)
for(int j=-1;j<2&&f;j+=2){
int w=(3*i*i+j*i)/2;
if(w*k>n){f=0;break;}
if(i%2==0)ans=(ans+B[n-w*k])%mod;
else ans=(ans-B[n-w*k]+mod)%mod;
}
printf("%d\n",ans);
}
return 0;
}