#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
using LL = long long;
LL f[88];

map<pair<int, LL>, LL> mp;
LL n, k;
int l;

LL dp(LL n){
    if (n <= k) return 0;
    if (mp.contains({n, k})) return mp[{n, k}];
    int r = upper_bound(f + 1, f + 88, n) - f - 1;
    LL ans = r - l + 1;
    for(int i = l; i + 1 <= r; i++){
        ans += dp(f[i + 1] - f[i] - 1);
    }
    ans += dp(n - f[r]);
    return mp[{n, k}] = ans;
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    f[0] = f[1] = 1;
    for(int i = 2; i < 88; i++){
        f[i] = f[i - 1] + f[i - 2];
    }

    int T;
    cin >> T;
    while(T--){
        cin >> k >> n;
        l = upper_bound(f + 1, f + 88, k) - f;
        cout << n - dp(n) << '\n';
    }

}