import java.util.Scanner;
 
/**
 * Created by Shreyans Sheth [bholagabbar] on 10/14/2015 at 7:23 PM using IntelliJ IDEA (Fast IO Template)
 */
 
class solve
{
    public static void main(String[] args) throws Exception
    {
        //System.setIn(new FileInputStream("E:/Shreyans/Documents/QBIT_2015/src/Q05/input.txt"));
        Scanner sc=new Scanner(System.in);
        int MOD=(int)(1e9)+7;
        int t=sc.nextInt();
        while(t-->0)
        {
            int n=sc.nextInt();
            int k=sc.nextInt();
            int[] dp=new int[n+1];
            for(int i=1;i<n;i++)
                dp[i]=1;//No 'k' consecutive reds possible. Only blue
            dp[k]=2;//Here 2 possible. k red and k blue
            for(int i=k+1;i<=n;i++)
                dp[i]=(dp[i-1]%MOD+dp[i-k]%MOD)%MOD;//Work out dp condition
            System.out.println(dp[n]);
        }
    }
}

aW1wb3J0IGphdmEudXRpbC5TY2FubmVyOwoKLyoqCiAqIENyZWF0ZWQgYnkgU2hyZXlhbnMgU2hldGggW2Job2xhZ2FiYmFyXSBvbiAxMC8xNC8yMDE1IGF0IDc6MjMgUE0gdXNpbmcgSW50ZWxsaUogSURFQSAoRmFzdCBJTyBUZW1wbGF0ZSkKICovCgpjbGFzcyBzb2x2ZQp7CiAgICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB0aHJvd3MgRXhjZXB0aW9uCiAgICB7CiAgICAgICAgLy9TeXN0ZW0uc2V0SW4obmV3IEZpbGVJbnB1dFN0cmVhbSgiRTovU2hyZXlhbnMvRG9jdW1lbnRzL1FCSVRfMjAxNS9zcmMvUTA1L2lucHV0LnR4dCIpKTsKICAgICAgICBTY2FubmVyIHNjPW5ldyBTY2FubmVyKFN5c3RlbS5pbik7CiAgICAgICAgaW50IE1PRD0oaW50KSgxZTkpKzc7CiAgICAgICAgaW50IHQ9c2MubmV4dEludCgpOwogICAgICAgIHdoaWxlKHQtLT4wKQogICAgICAgIHsKICAgICAgICAgICAgaW50IG49c2MubmV4dEludCgpOwogICAgICAgICAgICBpbnQgaz1zYy5uZXh0SW50KCk7CiAgICAgICAgICAgIGludFtdIGRwPW5ldyBpbnRbbisxXTsKICAgICAgICAgICAgZm9yKGludCBpPTE7aTxuO2krKykKICAgICAgICAgICAgICAgIGRwW2ldPTE7Ly9ObyAnaycgY29uc2VjdXRpdmUgcmVkcyBwb3NzaWJsZS4gT25seSBibHVlCiAgICAgICAgICAgIGRwW2tdPTI7Ly9IZXJlIDIgcG9zc2libGUuIGsgcmVkIGFuZCBrIGJsdWUKICAgICAgICAgICAgZm9yKGludCBpPWsrMTtpPD1uO2krKykKICAgICAgICAgICAgICAgIGRwW2ldPShkcFtpLTFdJU1PRCtkcFtpLWtdJU1PRCklTU9EOy8vV29yayBvdXQgZHAgY29uZGl0aW9uCiAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbihkcFtuXSk7CiAgICAgICAgfQogICAgfQp9

MQo0CjIK

1
4
2