#include
using namespace std;
int fun (int n,int m)
{
if (n=0)
{
return 0;
}
int x= fun(n-1,m) +fun(n-m,m);
return x;
}
int main() {
int n,m,t;
cin>>t;
for (int i=0;i<t;i++)
{
cin>>n;
cin>>m;
int x=fun(n,m);
cout<<x;
}
return 0;
}