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(CountWays(n,m));
t–;
}
sc.close();
}
public static int CountWays(int n, int m){
int count[]=new int[n+1];
count[0]=0;
for(int i=1;i<=n;i++){
if(i>m){
count[i] = count[i - 1] + count[i - m];
}
else if (i < m || i == 1){
count[i] = 1;
}
else{
count[i]=2;
}
}
return count[n];
}
}