public class TilingProblem {
private static void 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;
}
System.out.println(count[n]);
//return count[n];
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int n = 0,m = 0;
int t=sc.nextInt();
while(t>0) {
n=sc.nextInt();
m=sc.nextInt();
countWays(n, m);
t--;
}
}
}