#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 (k == F[n])
return X[n];
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+OwoKY29uc3QgaW50IE1PRCA9IDFlOSArIDc7CmNvbnN0IGludCBOID0gMWU1ICsgNTsKCmxsIG4sIGssIEZbNTBdLCBYWzUwXTsKCnZvaWQgcHJlcGFyZSgpIHsKICAgIEZbMF0gPSAxLCBGWzFdID0gMTsKICAgIEZPUihpLCAyLCA0OSkgewogICAgICAgIEZbaV0gPSBGW2kgLSAxXSArIEZbaSAtIDJdOwogICAgfQoKICAgIFhbMF0gPSAxLCBYWzFdID0gMDsKICAgIEZPUihpLCAyLCA0OSkgewogICAgICAgIFhbaV0gPSBYW2kgLSAxXSArIFhbaSAtIDJdOwogICAgfQp9CgpsbCBGaW5kKGxsIG4sIGxsIGspIHsKICAgIGlmIChrID09IEZbbl0pCiAgICAgICAgcmV0dXJuIFhbbl07CgogICAgaWYgKGsgPj0gRltuIC0gMV0pCiAgICAgICAgcmV0dXJuIFhbbiAtIDFdICsgRmluZChuIC0gMiwgayAtIEZbbiAtIDFdKTsKICAgIGVsc2UKICAgICAgICByZXR1cm4gRmluZChuIC0gMSwgayk7Cn0KCnZvaWQgcnVuX2Nhc2UoKSB7CiAgICBjaW4gPj4gbiA+PiBrOwoKICAgIGNvdXQgPDwgRmluZChuLCBrKSA8PCBlbmRsOwp9CgppbnQgbWFpbigpIHsKICAgIGNpbi50aWUoMCktPnN5bmNfd2l0aF9zdGRpbygwKTsKCiNpZmRlZiBKdWhhbjQwNAogICAgZnJlb3BlbigiRXJyb3IudHh0IiwgInciLCBzdGRlcnIpOwojZW5kaWYKCiAgICBpbnQgVCA9IDE7CiAgICBjaW4gPj4gVDsKCiAgICBwcmVwYXJlKCk7CgogICAgZm9yIChpbnQgdGVzdCA9IDE7IHRlc3QgPD0gVDsgKyt0ZXN0KSB7CgogICAgICAgIHJ1bl9jYXNlKCk7CiAgICB9CiAgICByZXR1cm4gMDsKfQ==