#ifndef Yamada
#define Yamada
#include Yamada __FILE__ Yamada

const int maxf = 89;

int F[maxf];
vector dp(maxf + 1, vector<int>(maxf + 1, 0));

void init() {
    F[0] = F[1] = 1;
    for (int i = 2; i < maxf; ++i) F[i] = F[i-1] + F[i-2];

    for (int i = 1; i < maxf; ++i) {
        for (int j = 1; j < maxf; ++j) {
            dp[i][j] = dp[i-1][j] + (i <= j);
            if (i >= 2) dp[i][j] += dp[i-2][j];
            // debug(i, j, dp[i][j]);
        }
    }
}

void solve() {
    int K, N; cin >> K >> N;
    int k = upper_bound(F, F + maxf, K) - F - 1;
    // debug(k);
    int ans = 0, pre = maxf + 1;
    for (int i = maxf - 1; i >= 1; --i) {
        if (N >= F[i]) {
            N -= F[i];

            ans += dp[i-1][k]; // len = i-1
            if (pre <= k) ++ans;
            pre = i;
        }
    }
    cout << ans << '\n';
}

signed main() {
    IOS();
    init();
    int t = 1; cin >> t;
    for (int i=1;i<=t;++i) solve();
    return 0;
}

#else

#ifdef local 
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize ("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define double __float80
using pii = pair<int, int>;
template <typename T> using MaxHeap = std::priority_queue<T>;
template <typename T> using MinHeap = std::priority_queue<T, vector<T>, greater<T>>;

#define SZ(a) ((int)(a).size())
#define ALL(a) begin(a), end(a)
#define RALL(a) rbegin(a), rend(a)
#define ee emplace
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
// #define X first
// #define Y second

#ifdef local
#define IOS() void()
#define debug(...) \
    fprintf(stderr, "\e[1;93m"), \
    fprintf(stderr, "At [%s], line %d: (%s) = ", __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), \
    fprintf(stderr, "\e[0m")
template <typename T> void _do(T &&_t) {cerr << _t << '\n';}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#define print(...) \
    fprintf(stderr, "\e[1;96m"), \
    _P(__VA_ARGS__), \
    fprintf(stderr, "\e[0m")
#else
#define IOS() ios_base::sync_with_stdio(0); cin.tie(0)
#define debug(...) void()
#define print(...) _P(__VA_ARGS__)
#define endl '\n'
#endif

template <typename U, typename V> bool chmin(U &u, V v) {return u > v ? u = v, 1 : 0;}
template <typename U, typename V> bool chmax(U &u, V v) {return u < v ? u = v, 1 : 0;}

template <typename T> void _P(T &&_x) {cout << _x << '\n';}
template <typename T, typename ...S> void _P(T &&_x, S &&..._t) {cout << _x << " "; _P(_t...);}

#endif