#include <iostream>
using namespace std;

int tileWays(int n, int m);

int main(int argc, char const *argv[])
{
    int T;
    cin>>T;
    int i = 0;
    int n,m;
    while(i++<T){
        cin>>n>>m;
        cout<<tileWays(n,m)<<endl;
    }
    return 0;
}

int tileWays(int n, int m)
{
    //base case
    if (n < 0)
        return 0;
    if (n == 0)
        return 1;
    if(n==m)
    return 2;
    
    //recursive case
    return tileWays(n - 1,m) + tileWays(n - m,m);
}