#include<bits/stdc++.h>
using namespace std;
int a,k,i,ans, f[50];
void rec(int x,int z,int k1)
{
    if(z<1)return;
    if(1ll*(k-k1)*f[z]<x)return;
    if(x==0)
    {
        if(k==k1)ans++;
        return;
    }
    if(k==k1)return;
    if(f[z]<=x)rec(x-f[z],z,k1+1);
    rec(x,z-1,k1);
}

int main()
{
    int tt, ii;
    cin>>tt;
    for (ii=1; ii<=tt; ii++)
    {
    ans=0;
    cin>>a>>k;
    f[1]=1;
    f[2]=2;
    for(i=3;i<=43;i++)
     f[i]=f[i-1]+f[i-2];
    rec(a,43,0);
    cout<<ans<<"\n";}
}