#include
using namespace std;
const unsigned int M = 1000000007;
int find(int n,int m)
{
if(n>0 && n<m)
return 1;
else if(n==m)
return 2;
return ((find(n-m,m)%M)+(find(n-1,m)%M)%M);
}
int main() {
int t;
cin>>t;
while(t–)
{
int n,m;
cin>>n>>m;
cout<<find(n,m)<<endl;
}
return 0;
}
