#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
#define ll long long
// MAX (long long) 1000000000000000000
// #define M 100 + 5
#define N 200
#define MOD (ll)1000000007
#define ld long double
#define sz size()
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
#define faster() \
ios_base::sync_with_stdio(0); \
cin.tie(NULL); \
cout.tie(NULL);
#define zero(n) setw(n) << setfill('0')
#define stp(n) fixed << setprecision(n)
int main() {
int t;
cin >> t;
ll f[50];
f[0] = 1;
f[1] = 0;
for (int i = 2; i <= 45; i++) {
f[i] = f[i - 1] + f[i - 2];
}
ll l[50];
l[0] = 1;
l[1] = 1;
for (int i = 2; i <= 45; i++) {
l[i] = l[i - 1] + l[i - 2];
}
while (t--) {
int n, k;
cin >> n >> k;
ll res = 0;
while (k > 0 && n >= 0) {
if (k == l[n]) {
res += f[n];
break;
}
if (k >= l[n - 1]) {
res += f[n - 1];
k -= l[n - 1];
n = n - 2;
}
else {
n = n - 1;
}
}
cout << res << endl;
}
return 0;
}
I2RlZmluZSBfQ1JUX1NFQ1VSRV9OT19XQVJOSU5HUwojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxjc3RkbGliPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPGlvbWFuaXA+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPG1hcD4KI2luY2x1ZGUgPG51bWVyaWM+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPHNzdHJlYW0+CiNpbmNsdWRlIDxzdGFjaz4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHVub3JkZXJlZF9tYXA+CiNpbmNsdWRlIDx1bm9yZGVyZWRfc2V0PgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBsbCBsb25nIGxvbmcKLy8gTUFYIChsb25nIGxvbmcpIDEwMDAwMDAwMDAwMDAwMDAwMDAKLy8gI2RlZmluZSBNIDEwMCArIDUKI2RlZmluZSBOIDIwMAoKI2RlZmluZSBNT0QgKGxsKTEwMDAwMDAwMDcKI2RlZmluZSBsZCBsb25nIGRvdWJsZQojZGVmaW5lIHN6IHNpemUoKQojZGVmaW5lIEZPUihpLCBhLCBiKSBmb3IgKGludCBpID0gYTsgaSA8PSBiOyBpKyspCiNkZWZpbmUgRk9SRChpLCBhLCBiKSBmb3IgKGludCBpID0gYTsgaSA+PSBiOyBpLS0pCiNkZWZpbmUgZmFzdGVyKCkgICAgICAgICAgICAgICAgICBcCiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOyBcCiAgICBjaW4udGllKE5VTEwpOyAgICAgICAgICAgICAgICBcCiAgICBjb3V0LnRpZShOVUxMKTsKI2RlZmluZSB6ZXJvKG4pIHNldHcobikgPDwgc2V0ZmlsbCgnMCcpCiNkZWZpbmUgc3RwKG4pIGZpeGVkIDw8IHNldHByZWNpc2lvbihuKQoKaW50IG1haW4oKSB7CiAgICBpbnQgdDsKICAgIGNpbiA+PiB0OwoKICAgIGxsIGZbNTBdOwogICAgZlswXSA9IDE7CiAgICBmWzFdID0gMDsKCiAgICBmb3IgKGludCBpID0gMjsgaSA8PSA0NTsgaSsrKSB7CiAgICAgICAgZltpXSA9IGZbaSAtIDFdICsgZltpIC0gMl07CiAgICB9CgogICAgbGwgbFs1MF07CiAgICBsWzBdID0gMTsKICAgIGxbMV0gPSAxOwogICAgZm9yIChpbnQgaSA9IDI7IGkgPD0gNDU7IGkrKykgewogICAgICAgIGxbaV0gPSBsW2kgLSAxXSArIGxbaSAtIDJdOwogICAgfQoKICAgIHdoaWxlICh0LS0pIHsKICAgICAgICBpbnQgbiwgazsKICAgICAgICBjaW4gPj4gbiA+PiBrOwoKICAgICAgICBsbCByZXMgPSAwOwoKICAgICAgICB3aGlsZSAoayA+IDAgJiYgbiA+PSAwKSB7CiAgICAgICAgICAgIGlmIChrID09IGxbbl0pIHsKICAgICAgICAgICAgICAgIHJlcyArPSBmW25dOwogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaWYgKGsgPj0gbFtuIC0gMV0pIHsKICAgICAgICAgICAgICAgIHJlcyArPSBmW24gLSAxXTsKICAgICAgICAgICAgICAgIGsgLT0gbFtuIC0gMV07CiAgICAgICAgICAgICAgICBuID0gbiAtIDI7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZSB7CiAgICAgICAgICAgICAgICBuID0gbiAtIDE7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIGNvdXQgPDwgcmVzIDw8IGVuZGw7CiAgICB9CgogICAgcmV0dXJuIDA7Cn0=