//Задача "Строки Фибоначчи-2"
//4-я Интернет-олимпиада сезона 2009-2010, усложненный уровень
//Автор задачи: Федор Царев, tsarev@rain.ifmo.ru
//Автор решения: Рустам Ганеев ganeev@rain.ifmo.ru

#include <iostream>

using namespace std;

#define REP(i, n) for(int i = 0; i < n; i++)

long long len[46], cnt[46];

long long calc(int n,int k){
	if (len[n] == k){
		return cnt[n];
	} else{
		if (k > len[n - 2]){
			return (cnt[n - 2] + calc(n - 1, k - len[n - 2]));
		} else{
			return calc(n - 2, k);
		}
	}
}
int main(){
	freopen("fib2.in", "r", stdin);
	freopen("fib2.out", "w", stdout);
	len[0] = 1;	len[1] = 1;
	cnt[0] = 1;	cnt[1] = 0;
	for (int i = 2; i < 46; i++){
		len[i] = len[i - 2] + len[i - 1];
		cnt[i] = cnt[i - 2] + cnt[i - 1];
	}
	int t;
	cin >> t;
	REP(i, t){
		int n, k;
		cin >> n >> k;
		cout << calc(n, k) << endl;
	}
	return 0;
}