#include <iostream>
using namespace std;

int countTiles(int n,int m){
    //Base case
    if(n>=1 && n<m)
    return 1;
    if(n==m)
    return 2;
    //recursive case
    else return(countTiles(n-1,m)+countTiles(n-m,m));
}

int main() {
	// your code goes here
	int t,n,m;
	cin>>t;
	while(t--) {
	    cin>>n>>m;
	    cout<<countTiles(n,m)<<endl;
	}
	return 0;
}