#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);
}

CiNpbmNsdWRlIDxpb3N0cmVhbT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCB0aWxlV2F5cyhpbnQgbiwgaW50IG0pOwoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIgY29uc3QgKmFyZ3ZbXSkKewogICAgaW50IFQ7CiAgICBjaW4+PlQ7CiAgICBpbnQgaSA9IDA7CiAgICBpbnQgbixtOwogICAgd2hpbGUoaSsrPFQpewogICAgICAgIGNpbj4+bj4+bTsKICAgICAgICBjb3V0PDx0aWxlV2F5cyhuLG0pPDxlbmRsOwogICAgfQogICAgcmV0dXJuIDA7Cn0KCmludCB0aWxlV2F5cyhpbnQgbiwgaW50IG0pCnsKICAgIC8vYmFzZSBjYXNlCiAgICBpZiAobiA8IDApCiAgICAgICAgcmV0dXJuIDA7CiAgICBpZiAobiA9PSAwKQogICAgICAgIHJldHVybiAxOwogICAgaWYobj09bSkKICAgIHJldHVybiAyOwogICAgCiAgICAvL3JlY3Vyc2l2ZSBjYXNlCiAgICByZXR1cm4gdGlsZVdheXMobiAtIDEsbSkgKyB0aWxlV2F5cyhuIC0gbSxtKTsKfQ==

MgoyIDMKNCA0Cg==

2
2 3
4 4