#include
#include<math.h>
using namespace std;
long long countWays(int n,int m,int *p){
if(n<0){
return 0;
}
if(n==1){
return 1;
}
if(n==m){
return 2;
}
if(p[n] != 0){
return p[n];
}
else{
p[n] = countWays(n-1,m,p) + countWays(n-m,m,p);
return p[n];
}
}
int main() {
int t,n,m;
cin>>t;
while(t--){
cin>>n>>m;
int arr[100000] = {0};
cout<<countWays(n,m,arr) % ((long long)pow(10,9) + 7)<<endl;
}
return 0;
}