#include <cstdio>
#include <cstring>
typedef long long ll;
int T;bool v[105];
ll n,k,f[105],dp[105];
ll DP(int p,bool bound,bool lst){
if(p < k)return 1;
if(!lst&&!bound&&~dp[p])return dp[p];
ll r = 0;
r += DP(p-1,bound&(v[p]==0),0);
if(!lst && (!bound || v[p] == 1))
r += DP(p-1,bound,1);
if(!lst&&!bound)dp[p] = r;
return r;
}
int main(){
scanf("%d",&T);
f[1] = 1,f[2] = 2;
for(int i=3;i<=90;++i)f[i] = f[i-1] + f[i-2];
while(T--){
scanf("%lld %lld",&k,&n),--n;
ll tn = n;memset(v,0,sizeof(v));
ll tk = k;for(int i=90;i;--i)if(f[i]>tk)k=i;
for(int i=90;i;--i)if(tn>=f[i])tn-=f[i],v[i]=1;
memset(dp,-1,sizeof(dp)),printf("%lld\n",n-DP(90,1,0)+1);
}
return 0;
}
