#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define max 100001
typedef long long ll;

ll rec(ll n, ll m, map<ll,ll>dp){
    if(n<0 || m<0)
        return 0;
    if(n==0)
        return 1;
    if(dp.find(n)!=dp.end()){
    	return dp[n];
    }
    else{
        ll a = rec(n-1,m, dp)%mod;
        ll b = 0;
        if(m<=n)
            b = rec(n-m, m, dp)%mod;
        dp[n] = (a+b)%mod;
        return dp[n];
    }
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin>>t;
	while(t--){
	    ll n,m;
        cin>>n>>m;
        map<ll,ll>dp;
        ll ans = rec(n,m,dp);
        cout<<ans<<endl;
	}
	return 0;
}