import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t–>0)
{
int n=sc.nextInt();
int m=sc.nextInt();
System.out.println(Tiling(n,m)%1000000007);
}
}
public static int Tiling(int n,int m)
{
if(n==0)
return 1;
else if(n<0)
return 0;
else{
return Tiling(n-1,m)+Tiling(n-m,m);
}
}
}