#include<bits/stdc++.h>
using namespace std;
#define ll long long
int find(int n,int m){
//if(n<=3)
// return 0;
return find(n-m,m)+find(n-1,m);
}
int main(){
int t;
ll n,m;
cin>>t;
while(t–){
cin>>n>>m;
int x=find(n,m);
cout<<x<<endl;
}
return 0;
}