import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;


public class fib2_ft {
	
	private static final int MAX_T = 100;
	private static final int MAX_N = 45;
	static int[] len;
	static int[] cnt;
	
	private static void myAssert(boolean u, String message) {
		if (!u) {
			throw new Error("Assertion failed!!! " + message);
		}
	}

	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(new File("fib2.in"));
		PrintWriter out = new PrintWriter(new FileWriter(new File("fib2.out")));
		int t = in.nextInt();
		myAssert((1 <= t) && (t <= MAX_T), "t is out of bounds: " + t);
		len = new int[46];
		cnt = new int[46];
		len[0] = 1;
		len[1] = 1;
		cnt[0] = 1;
		cnt[1] = 0;
		for (int i = 2; i < len.length; i++) {
			len[i] = len[i - 1] + len[i - 2];
			cnt[i] = cnt[i - 1] + cnt[i - 2];
		}
		for (int tt = 0; tt < t; tt++) {
			int n = in.nextInt();
			myAssert((0 <= n) && (n <= MAX_N), "n is ouf of bounds: " + n);
			int k = in.nextInt();
			myAssert((1 <= k) && (k <= len[n]), "k is out of bounds: " + k);
			out.println(solve(n, k));
		}
		out.close();
	}

	private static int solve(int n, int k) {
		if (k == len[n]) {
			return cnt[n];
		}
		if (k <= len[n - 2]) {
			return solve(n - 2, k);
		} else {
			return solve(n - 2, len[n - 2]) + solve(n - 1, k - len[n - 2]);
		}
	}
}
