#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (auto i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (auto i = (a); i >= (b); --i)
#define sz(x) (int)(x).size()
#define pb push_back
#define ppb pop_back
#define endl '\n'
#define fi first
#define se second
#ifdef Juhan404
#include "debug.h"
#else
#define debug(...)
#endif
using ll = long long;
using pii = pair<int, int>;
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
ll n, k, F[50], X[50];
void prepare() {
F[0] = 1, F[1] = 1;
FOR(i, 2, 49) {
F[i] = F[i - 1] + F[i - 2];
}
X[0] = 1, X[1] = 0;
FOR(i, 2, 49) {
X[i] = X[i - 1] + X[i - 2];
}
}
ll Find(ll n, ll k) {
if (n == 0)
return 1;
if (n == 1)
return 0;
if (k == F[n])
return X[n];
if (k == F[n - 1])
return X[n - 1];
if (k > F[n - 1])
return X[n - 1] + Find(n - 2, k - F[n - 1]);
else
return Find(n - 1, k);
}
void run_case() {
cin >> n >> k;
cout << Find(n, k) << endl;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
#ifdef Juhan404
freopen("Error.txt", "w", stderr);
#endif
int T = 1;
cin >> T;
prepare();
for (int test = 1; test <= T; ++test) {
run_case();
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIEZPUihpLCBhLCBiKSBmb3IgKGF1dG8gaSA9IChhKTsgaSA8PSAoYik7ICsraSkKI2RlZmluZSBST0YoaSwgYSwgYikgZm9yIChhdXRvIGkgPSAoYSk7IGkgPj0gKGIpOyAtLWkpCiNkZWZpbmUgc3ooeCkgKGludCkoeCkuc2l6ZSgpCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgcHBiIHBvcF9iYWNrCiNkZWZpbmUgZW5kbCAnXG4nCiNkZWZpbmUgZmkgZmlyc3QKI2RlZmluZSBzZSBzZWNvbmQKCiNpZmRlZiBKdWhhbjQwNAojaW5jbHVkZSAiZGVidWcuaCIKI2Vsc2UKI2RlZmluZSBkZWJ1ZyguLi4pCiNlbmRpZgoKdXNpbmcgbGwgPSBsb25nIGxvbmc7CnVzaW5nIHBpaSA9IHBhaXI8aW50LCBpbnQ+OwoKY29uc3QgaW50IE1PRCA9IDFlOSArIDc7CmNvbnN0IGludCBOID0gMWU1ICsgNTsKCmxsIG4sIGssIEZbNTBdLCBYWzUwXTsKCnZvaWQgcHJlcGFyZSgpIHsKICAgIEZbMF0gPSAxLCBGWzFdID0gMTsKICAgIEZPUihpLCAyLCA0OSkgewogICAgICAgIEZbaV0gPSBGW2kgLSAxXSArIEZbaSAtIDJdOwogICAgfQoKICAgIFhbMF0gPSAxLCBYWzFdID0gMDsKICAgIEZPUihpLCAyLCA0OSkgewogICAgICAgIFhbaV0gPSBYW2kgLSAxXSArIFhbaSAtIDJdOwogICAgfQp9CgpsbCBGaW5kKGxsIG4sIGxsIGspIHsKICAgIGlmIChuID09IDApCiAgICAgICAgcmV0dXJuIDE7CiAgICBpZiAobiA9PSAxKQogICAgICAgIHJldHVybiAwOwoKICAgIGlmIChrID09IEZbbl0pCiAgICAgICAgcmV0dXJuIFhbbl07CiAgICBpZiAoayA9PSBGW24gLSAxXSkKICAgICAgICByZXR1cm4gWFtuIC0gMV07CgogICAgaWYgKGsgPiBGW24gLSAxXSkKICAgICAgICByZXR1cm4gWFtuIC0gMV0gKyBGaW5kKG4gLSAyLCBrIC0gRltuIC0gMV0pOwogICAgZWxzZQogICAgICAgIHJldHVybiBGaW5kKG4gLSAxLCBrKTsKfQoKdm9pZCBydW5fY2FzZSgpIHsKICAgIGNpbiA+PiBuID4+IGs7CgogICAgY291dCA8PCBGaW5kKG4sIGspIDw8IGVuZGw7Cn0KCmludCBtYWluKCkgewogICAgY2luLnRpZSgwKS0+c3luY193aXRoX3N0ZGlvKDApOwoKI2lmZGVmIEp1aGFuNDA0CiAgICBmcmVvcGVuKCJFcnJvci50eHQiLCAidyIsIHN0ZGVycik7CiNlbmRpZgoKICAgIGludCBUID0gMTsKICAgIGNpbiA+PiBUOwoKICAgIHByZXBhcmUoKTsKCiAgICBmb3IgKGludCB0ZXN0ID0gMTsgdGVzdCA8PSBUOyArK3Rlc3QpIHsKCiAgICAgICAgcnVuX2Nhc2UoKTsKICAgIH0KICAgIHJldHVybiAwOwp9