#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)
//         return 0;
//     if(n==0)
//         return 1;
//     // else if(n==m)
//     //     return 2;
//     if(dp.find(n)!=dp.end()){
//     	return dp[n];
//     }
//     else{
//         ll a = rec(n-1,m, dp)%mod;
//         ll 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 dp[n+1]={0};
        dp[0]=1;
        dp[1]=1;
        for(ll i=2; i<=n; i++){
            dp[i] = (dp[i]%mod + dp[i-1]%mod)%mod;
            if(i>=m)
                dp[i] = (dp[i]%mod + dp[i-m]%mod)%mod;
        }
        cout<<dp[n]<<endl;
	}
	return 0;
}