#include <bits/stdc++.h>
#define MAX 50
using namespace std;

int t, c[MAX], a[MAX];

int Calc(int n, int k)
{
    if (k>=c[n]) return a[n];

    if (k>c[n-2])
    {
        return Calc(n-1,k-c[(n-2)])+a[n-2];
    }

    return Calc(n-2, k);


}

int main()
{
    c[0]=1, c[1]=1;
    a[0]=1, a[1]=0;

    for (int i=2; i<=MAX; i++)
    {
        c[i]=c[i-1]+c[i-2];
        a[i]=a[i-1]+a[i-2];
    }

    cin >> t;
    int n,k;
    while (t--)
    {
        cin >> n >> k;
        cout<<Calc(n,k)<<endl;
    }


    return 0;
}