#include
using namespace std;
using namespace std;
int tiling_prob(int n,int m){
//base condition
if(n<m)
return 1;
else if(n==m)
return 2;
else{
//recursion condition
return (tiling_prob(n-1,m) + tiling_prob(n-m,m));
}
}
int main() {
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
long long int t=tiling_prob(n,m)%(10^9+7);
cout<<t<<endl;
}
}
ttl is coming in 4 cases