// Arup Guha
// 9/7/2013
// Solution to UCF JV Practice Problem D: Truck Loads

import java.util.*;

public class d {

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();

		// Process each case.
		for (int loop=0; loop<numCases; loop++) {

			int n = stdin.nextInt();
			int k = stdin.nextInt();
			int[] memo = new int[n+1];

			// Set up memoization.
			Arrays.fill(memo,-1);
			for (int i=1; i<=k; i++)
				memo[i] = 1;

			// Solve and output.
			int ans = solve(n,k,memo);
			System.out.println(ans);
		}
	}

	public static int solve(int n, int k, int[] memo) {

		// We know the answer already...
		if (memo[n] != -1) return memo[n];

		// Note: This handles the odd case without an if statement...(and the even case, of course...)
		// We just do what the problem says, split the stack in two and add up the totals...
		memo[n] = solve(n/2, k, memo) + solve((n+1)/2, k, memo);
		return memo[n];
	}
}