Chef is given a contract to build towers in Chefland which are made by stacking blocks one above the other. Initially, there is only 1 block in the inventory and no tower has been built. Chef follows the following 2 steps in each operation:

Either build a new tower or update an existing tower that has been built in previous operations using any number of blocks currently present in the inventory. After this step, the size of the inventory reduces by the number of blocks used.
Suppose the tower Chef updated or built has B blocks after the step, Chef gets to add B new blocks to the inventory as a reward.

Find the maximum number of towers of height X that Chef can build in M operations.

Note: Tower of height X means that the tower consists of X blocks placed one above the other.

------ Input Format ------ 

- First line will contain T, number of test cases. Then the test cases follow.
- Each test case contains a single line of input, two space separated integers X, M.

------ Output Format ------ 

For each test case, output a single integer, the maximum number of towers that Chef can build.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ X ≤ 10^{9}$
$0 ≤ M ≤ 10^{17}$

----- Sample Input 1 ------ 
4
2 1
2 2
2 3
53 7
----- Sample Output 1 ------ 
0
1
2
1

----- explanation 1 ------ 
Test Cases $1$, $2$ and $3$:
- Operation $1$: 
- Remove $1$ block from the inventory and build a new tower of height $1$ after which the inventory becomes empty. 
- Add $1$ block to the inventory after which the inventory has only $1$ block.
- Operation $2$: 
- Remove $1$ block from the inventory and update the tower of height $1$ to $1 + 1 = 2$ after which the inventory becomes empty.
- Add $2$ blocks to the inventory after which the inventory has only $2$ blocks.
- Operation $3$:
- Remove $2$ blocks from the inventory and build a new tower of height $2$ after which the inventory becomes empty.
- Add $2$ blocks to the inventory after which the inventory has only $2$ blocks.

So after operation $1$, there is no tower of height $2$ built, after operation $2$, there is a single tower of height $2$ built and after operation $3$, $2$ towers of height $2$ are built.

Test Case $4$:
- Operation $1$: 
- Remove $1$ block from the inventory and build a new tower of height $1$ after which the inventory becomes empty. 
- Add $1$ block to the inventory after which the inventory has only $1$ block.
- Operation $2$: 
- Remove $1$ block from the inventory and update the tower of height $1$ to $1 + 1 = 2$ after which the inventory becomes empty.
- Add $2$ blocks to the inventory after which the inventory has only $2$ blocks.
- Operation $3$: 
- Remove $2$ blocks from the inventory and update the tower of height $2$ to $2 + 2 = 4$ after which the inventory becomes empty.
- Add $4$ blocks to the inventory after which the inventory has only $4$ blocks.
- Operation $4$: 
- Remove $4$ blocks from the inventory and update the tower of height $4$ to $4 + 4 = 8$ after which the inventory becomes empty.
- Add $8$ blocks to the inventory after which the inventory has only $8$ blocks.
- Operation $5$: 
- Remove $8$ blocks from the inventory and update the tower of height $8$ to $8 + 8 = 16$ after which the inventory becomes empty.
- Add $16$ blocks to the inventory after which the inventory has only $16$ blocks.
- Operation $6$: 
- Remove $16$ blocks from the inventory and update the tower of height $16$ to $16 + 16 = 32$ after which the inventory becomes empty.
- Add $32$ blocks to the inventory after which the inventory has only $32$ blocks.
- Operation $7$: 
- Remove $21$ blocks from the inventory and update the tower of height $32$ to $32 + 21 = 53$ after which the inventory has $32 - 21 = 11$ blocks remaining.
- Add $53$ blocks to the inventory after which the inventory has $53 + 11 = 64$ blocks in total.

So after $7^{th}$ operation we are able to achieve one tower of height $53$.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import math
t = int(input())
while t != 0:
	(x, m) = map(int, input().split())
	if x == 0:
		print(0)
		t = t - 1
		continue
	a = math.ceil(math.log(x, 2))
	ans = m - a
	if m > a:
		print(ans)
	else:
		print(0)
	t -= 1


from math import ceil, log

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())

def main():
	for i in range(inp()):
		(X, M) = lis()
		ans = M - ceil(log(X, 2))
		if ans < 0:
			print(0)
		else:
			print(ans)
main()


import math
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	required = math.ceil(math.log(n, 2)) + 1
	print(max(m - required, -1) + 1)


for _ in range(int(input())):
	(x, m) = map(int, input().split())
	i = 1
	while x > 1:
		x /= 2
		i += 1
	if m < i:
		print(0)
	else:
		print(m - i + 1)


from math import ceil

def moves_to_build(h):
	moves = 1
	while h > 1:
		h = ceil(h / 2)
		moves += 1
	return moves
T = int(input())
for i in range(T):
	(h, moves) = map(int, input().split())
	print(max(0, 1 + moves - moves_to_build(h)))


import math
for _ in range(int(input())):
	(n, x) = list(map(int, input().split()))
	m = math.ceil(math.log2(n)) + 1
	print(max(0, x - m + 1))


from sys import stdin
from collections import Counter

def building_tower():
	(x, m) = map(int, stdin.readline().strip().split(' '))
	temp = 2
	towers = 0
	while temp <= x:
		temp <<= 1
		towers += 1
	temp /= 2
	temp2 = towers + 1
	if temp2 > m:
		print(0)
		return
	if temp == x:
		print(1 + (m - temp2))
	else:
		print(m - temp2)
t = int(stdin.readline().strip())
while t > 0:
	building_tower()
	t -= 1


import math
for tastcas in range(int(input())):
	(x, m) = list(map(int, input().split()))
	if x == 1:
		print(m)
		continue
	c = int(math.log(x - 1) / math.log(2)) + 1
	if c > m:
		print(0)
	else:
		print(m - c)


for _ in range(int(input())):
	(x, m) = map(int, input().split())
	b = 1
	m -= 1
	if m == 0 and x > 1:
		print(0)
		continue
	while b < x and m > 0:
		b *= 2
		m -= 1
	if b >= x and m >= 0:
		print(m + 1)
	else:
		print(0)


for _ in range(int(input())):
	(x, m) = map(int, input().split())
	a = 0
	while 1:
		if x <= pow(2, a):
			break
		a += 1
	if a > m:
		print(0)
	else:
		print(m - a)


import sys, os
from sys import stdin, stdout
io_path = '/Users/kunaldubey/Projects/competitve-programming/IO'
if os.path.exists(io_path):
	sys.stdout = open(io_path + '/output.txt', 'w')
	sys.stdin = open(io_path + '/input.txt', 'r')

def get_ints():
	return map(int, input().strip().split())

def get_ints_list():
	return list(map(int, input().strip().split()))

def get_string():
	return input().strip()
test_cases = int(input())
while test_cases > 0:
	(x, m) = get_ints()
	blocks = 1
	initial_height = 0
	operation = 0
	while initial_height < x:
		initial_height = pow(2, operation)
		operation += 1
	if operation <= m:
		print(m - operation + 1)
	else:
		print(0)
	test_cases -= 1


import math
for t in range(int(input())):
	(x, m) = map(int, input().split())
	n = math.ceil(math.log(x, 2))
	if n > m:
		print(0)
	else:
		print(m - n)


import math
tc = int(input())
for e in range(tc):
	l = input().split(' ')
	l1 = int(l[1])
	logx = math.log(int(l[0]), 2)
	if logx >= l1:
		print(0)
		continue
	if logx == int(logx):
		print(int(l[1]) - int(logx))
		continue
	print(int(l[1]) - int(logx) - 1)


for i in range(int(input())):
	(x, m) = map(int, input().split())
	i = 0
	mh = 0
	while i < m:
		if 2 ** i >= x:
			mh = 1
			i += 1
			break
		i += 1
	print(mh + m - i)


import math
for _ in range(int(input())):
	(x, m) = map(int, input().split())
	logval = math.log(x, 2)
	steps = int(logval) + 1
	ans = m - steps
	if ans >= 0:
		if int(logval) - logval == 0:
			ans += 1
	else:
		ans = 0
	print(ans)


import math, os, io, heapq
from functools import reduce
from sys import stdin, stdout
from collections import Counter, deque, defaultdict
from itertools import product
import bisect

def getList(method=int):
	return list(map(method, input().split()))

def getInt():
	return int(input())

def solve():
	(x, m) = getList()
	x = int(x)
	first = x.bit_length() + (x ^ 1 << x.bit_length() - 1 > 0)
	if first > m:
		return 0
	return m - first + 1
for _ in range(getInt()):
	print(solve())


def solve():
	(X, M) = map(int, input().split())
	blocks = 1
	while blocks < X and M > 0:
		M -= 1
		blocks *= 2
	return M
t = int(input())
for _ in range(t):
	print(solve())


import math
for _ in range(int(input())):
	(x, m) = map(int, input().split())
	n = math.ceil(math.log2(x)) + 1
	if n > m:
		print(0)
	else:
		print(m - n + 1)


from math import log2

def solve():
	(H, M) = map(int, input().split())
	ops = int(log2(H))
	if pow(2, ops) < H:
		ops += 1
	ops += 1
	if ops > M:
		print(0)
		return
	print(M - ops + 1)
t = int(input())
for _ in range(t):
	solve()


import math
t = int(input())
while t:
	t -= 1
	(x, m) = map(int, input().split())
	steps = math.ceil(math.log2(x) + 1)
	if steps > m:
		print(0)
	else:
		print(m - steps + 1)


import math
t = int(input())
while t != 0:
	(x, m) = [int(i) for i in input().split()]
	y = math.ceil(math.log2(x)) + 1
	if m < y:
		print('0')
	else:
		print(m - y + 1)
	t -= 1


t = int(input())
for T in range(t):
	(X, M) = map(int, input().split())
	H = 0
	I = 1
	R = 0
	K = M + 1
	while K > 0:
		if X > H:
			H += I
			I = H
		else:
			break
		K -= 1
	R += K
	print(R)


import math

def solve_TOWERTOP(x: int, m: int):
	inv = 1
	to_get_to_x_height = math.ceil(math.log2(x))
	if to_get_to_x_height > m:
		return 0
	return m - to_get_to_x_height
T = int(input())
for i in range(T):
	(x, m) = tuple(map(int, input().split()))
	print(solve_TOWERTOP(x, m))


t = int(input())
for _ in range(t):
	(x, m) = list(map(int, input().split()))
	rem = 1
	towers = 0
	h = 0
	while h < x and m > 0:
		k = min(x - h, rem)
		h += k
		rem = h
		m -= 1
	if m == 0 and h < x:
		ans = 0
	else:
		towers += 1
		ans = towers + m
	print(ans)


t = int(input())
while t > 0:
	t -= 1
	[s1, s2] = input().split()
	x = int(s1)
	m = int(s2)
	op = 1
	h = 1
	while h < x:
		h *= 2
		op += 1
	if op > m:
		print(0)
	else:
		print(m - op + 1)


import sys
import bisect
inp = sys.stdin.readline

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)
for _ in range(int(inp())):
	(x, m) = map(int, inp().split())
	c = 1
	p = 1
	while x > p:
		c += 1
		p *= 2
	m = m - c
	print(m + 1) if m >= 0 else print(0)


T = int(input())
for tx in range(T):
	(X, M) = map(int, input().split())
	if X == 1:
		print(M)
	else:
		print(max(0, M - (X - 1).bit_length()))


import math
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	c = math.ceil(math.log2(x)) + 1
	if c > y:
		print(0)
	else:
		print(y - c + 1)


try:
	T = int(input())
	XM = []
	for _ in range(T):
		(x, y) = map(int, input().split())
		XM.append([x, y])
	for element in XM:
		expo = len(bin(element[0])) - 2
		if element[0] == pow(2, expo - 1):
			reqOperations = expo
		else:
			reqOperations = expo + 1
		temp = element[1] - reqOperations
		if temp >= 0:
			print(temp + 1)
		else:
			print(0)
except EOFError():
	pass


import math
t = int(input())
for i in range(t):
	l = [int(n) for n in input().split()]
	x = l[0]
	m = l[1]
	c = math.ceil(math.log2(x)) + 1
	if c > m:
		print(0)
	else:
		print(m - c + 1)


import math, bisect, heapq, random, sys, itertools
ints = lambda : list(map(int, input().split()))
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
p = 10 ** 9 + 7
for t in range(int(input())):
	(n, m) = ints()
	x = n
	c = -1
	while x:
		c += 1
		x //= 2
	if 2 ** c != n:
		c += 1
	if c > m:
		print(0)
	else:
		print(m - c)


import math
t = int(input())
for z in range(t):
	(h, m) = map(int, input().split())
	k = math.ceil(math.log2(h)) + 1
	if k > m:
		print(0)
	else:
		print(m - k + 1)


import math
t = int(input())
while t > 0:
	(x, m) = map(int, input().split())
	y = int(math.log(x, 2))
	if 2 ** y != x:
		y += 1
	if y >= m:
		print(0)
	else:
		print(m - y)
	t -= 1


T = int(input())
for i in range(T):
	arr = list(map(int, input().split()))
	build = 0
	height = arr[0]
	moves = arr[1]
	inv = 1
	xh = 0
	while moves > 0:
		moves -= 1
		xh += min(height - xh, inv)
		inv -= min(height - xh, inv)
		inv += xh
		if xh == height:
			build += 1
			xh = 0
		if inv >= height:
			break
	build += moves
	print(str(build))


from collections import defaultdict
import heapq
import math
from math import sqrt
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = 0
	if x == 0:
		print(0)
		continue
	h = 10000
	while l <= h:
		m = (l + h) // 2
		if pow(2, m) >= n:
			ans = m
			h = m - 1
		else:
			l = m + 1
	ans += 1
	if x - ans + 1 < 0:
		print(0)
	else:
		print(x - ans + 1)


import math
t = int(int(input()))
for i in range(t):
	(x, m) = map(int, input().split())
	if m == 0:
		print(0)
	else:
		count = 0
		for i in range(1, m + 1):
			power = math.pow(2, i - 1)
			if power >= x:
				d = m - i
				count += d + 1
				break
		print(count)


import math
t = int(input())
test = []
for i in range(t):
	v = [int(j) for j in input().split()]
	test.append(v)
for i in test:
	h = i[0]
	x = i[1]
	c = math.ceil(math.log2(h)) + 1
	if x < c:
		print(0)
	elif x == c:
		print(1)
	else:
		print(x - c + 1)


from math import log2
from math import ceil
for _ in range(int(input())):
	(x, m) = map(int, input().split())
	res = 10 ** 10
	if m < ceil(log2(x)) + 1:
		res = 0
	else:
		res = m - ceil(log2(x))
	print(res)


import math
for _ in range(int(input())):
	(x, m) = map(int, input().split())
	req = math.ceil(math.log(x, 2)) + 1
	if m < req:
		print(0)
	elif m == req:
		print(1)
	else:
		print(m - req + 1)


import math
T = int(input())
for i in range(T):
	(x, m) = [int(X) for X in input().split()]
	b = math.log(x, 2)
	if b == int(b):
		a = int(b) + 1
	else:
		a = int(b) + 2
	if a > m:
		print(0)
	else:
		print(1 + m - a)


from math import log, ceil
test = int(input())
for _ in range(test):
	(H, S) = list(map(int, input().split()))
	H_log = log(H, 2)
	base_2 = ceil(H_log)
	if base_2 > S - 1:
		print('0')
	elif base_2 == S - 1:
		print('1')
	else:
		print(S - base_2)


from math import log2, ceil
for _ in range(int(input())):
	(x, m) = map(int, input().split())
	ans = m - ceil(log2(x))
	if ans > 0:
		print(ans)
	else:
		print(0)


for _ in range(int(input())):
	(x, n) = map(int, input().split())
	s = bin(x)
	l = len(s) - 2
	if x == 1:
		print(n)
	elif s.count('1') == 1:
		if n < l:
			print(0)
		else:
			print(n - l + 1)
	else:
		l = l + 1
		if n < l:
			print(0)
		else:
			print(n - l + 1)


import math
for _ in range(int(input())):
	(x, m) = [int(x) for x in input().split()]
	n = math.ceil(math.log(x, 2)) + 1
	if m < n:
		print(0)
	else:
		print(m - n + 1)


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	m = math.ceil(math.log2(a) + 1)
	if b < m:
		print(0)
	else:
		print(b - m + 1)


import math
for _ in range(int(input())):
	(x, m) = map(int, input().split())
	k = math.log(x, 2)
	k = math.ceil(k)
	if m < k:
		print(0)
	else:
		print(m - k)


import math
for _ in range(int(input())):
	(X, M) = map(int, input().strip().split())
	count = 0
	N = math.ceil(math.log2(X)) + 1
	if M < N:
		print(0)
	else:
		print(M - N + 1)


import math
t = int(input())
for _ in range(t):
	(X, M) = map(int, input().split())
	y = math.ceil(math.log(X, 2))
	if M < math.log(X, 2) + 1:
		print(0)
	else:
		print(M - y)


import math
T = int(input())
for _ in range(T):
	(X, M) = map(int, input().split(' '))
	n = math.ceil(math.log2(X)) + 1
	if M < n:
		print(0)
	else:
		print(M - n + 1)


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
a = []
(n, k) = (0, 0)
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07
gp = []
ans = []

def update_it(bit, i, val):
	n = len(bit)
	while i < n:
		bit[i] += val
		i += i & -i

def get_ans(bit, i):
	n = len(bit)
	tot = 0
	while i > 0:
		tot += bit[i]
		i -= i & -i
	return tot

def flip(a, l, r):
	for i in range(l, r):
		a[i] = '0' if a[i] == '1' else '1'
	return

def hnbhai(tc):
	(x, m) = sd()
	req = 1
	sz = 1
	tot = 1
	while tot < x:
		tot += sz
		sz *= 2
		req += 1
	left = m - req
	if left < 0:
		print(0)
		return
	print(left + 1)
for _ in range(sb()):
	hnbhai(_ + 1)


import math
for _ in range(int(input())):
	arr = [int(i) for i in input().split()]
	n = math.ceil(math.log(arr[0], 2)) + 1
	if arr[1] < n:
		print(0)
	else:
		print(arr[1] - n + 1)


t = int(input())
for _ in range(t):
	(x, m) = map(int, input().split())
	h = 0
	prev = 1
	c = 0
	while h < x and m > 0:
		h += prev
		prev = h
		m -= 1
	if h >= x:
		h = 0
		c += 1
	print(c + m)


import sys
from math import sqrt, ceil, floor, gcd
from collections import Counter, defaultdict

def int_arr():
	return list(map(int, input().split()))

def str_arr():
	return list(map(str, input().split()))

def get_str():
	return map(str, input().split())

def get_int():
	return map(int, input().split())

def get_flo():
	return map(float, input().split())

def lcm(a, b):
	return a * b // gcd(a, b)
mod = 1000000007

def solve():
	(x, m) = get_int()
	h = 0
	prev = 1
	c = 0
	while h < x and m > 0:
		h += prev
		prev = h
		m -= 1
	if h >= x:
		h = 0
		c += 1
	print(c + m)
T = 1
T = int(input())
while T:
	solve()
	T -= 1


import math
t = int(input())
while t > 0:
	t -= 1
	k = 0
	(x, m) = map(int, input().split())
	n = math.ceil(math.log(x, 2)) + 1
	if m < n:
		print(k)
	else:
		print(m - n + 1)


t = int(input())
for i in range(t):
	[x, m] = list(map(int, input().split()))
	c = 1
	f = 0
	cou = 0
	while x != f and m != 0:
		if f + c < x:
			f = f + c
			c = f
			m -= 1
		elif f + c == x:
			cou = 1
			f = x
			c = x
			m -= 1
		else:
			cou = 1
			f = x
			c = x
			m -= 1
	if m > 0:
		cou += m
	print(cou)


import math
for i in range(int(input())):
	(height, operations) = [int(z) for z in input().split()]
	base_operation_cost = math.ceil(math.log(height, 2))
	if operations < base_operation_cost:
		print(0)
	else:
		print(operations - base_operation_cost)


for _ in range(int(input())):
	(x, m) = map(int, input().split())
	inv = 1
	ops = 0
	blocks = 0
	while blocks < x:
		blocks += inv
		inv = blocks
		ops += 1
	if ops > m:
		print(0)
	else:
		print(1 + m - ops)


for _ in range(int(input())):
	(x, m) = map(int, input().split())
	(h, op) = (1, 1)
	while h < x:
		h *= 2
		op += 1
	if op > m:
		print(0)
	elif op == m:
		print(1)
	else:
		print(m - op + 1)


t = int(input())
while t:
	(x, m) = map(int, input().split(' '))
	if m == 0:
		print(0)
		t -= 1
		continue
	(h, m) = (1, m - 1)
	while m != 0 and h < x:
		h *= 2
		m -= 1
	if h >= x:
		print(1 + m)
	else:
		print(0)
	t -= 1


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = 1
	i = 0
	k = 0
	while True:
		if 2 ** i >= a:
			k = i
			break
		i += 1
	if k < b:
		print(b - k)
	else:
		print(0)


from math import log, ceil
for _ in range(int(input())):
	(x, m) = map(int, input().split())
	op = ceil(log(x, 2)) + 1
	op = m - op
	if op < 0:
		print(0)
	else:
		print(op + 1)


t = int(input())
while t > 0:
	(x, m) = map(int, input().split())
	ht = 1
	moves = 1
	while ht < x:
		moves += 1
		ht *= 2
	if moves > m:
		print('0')
	else:
		print(1 + (m - moves))
	t = t - 1


t = int(input())
for _ in range(t):
	(x, m) = map(int, input().split())
	y = 1
	o = 1
	while y < x:
		y = y * 2
		o += 1
	if o > m:
		print(0)
	elif o == m:
		print(1)
	else:
		print(m - o + 1)


for _ in range(int(input())):
	(x, m) = map(int, input().split())
	inv = 1
	count = curr_height = steps = 0
	while curr_height < x:
		curr_height += min(inv, x - curr_height)
		inv = inv - min(inv, x - curr_height) + curr_height
		steps += 1
	if steps > m:
		print(0)
	else:
		print(m - steps + 1)


import math
t = int(input())
for ii in range(t):
	(x, m) = list(map(int, input().split()))
	a = math.ceil(math.log(x, 2)) + 1
	if a > m:
		print(0)
	else:
		print(m - a + 1)


try:
	x = int(input())
	for _ in range(x):
		ip = input()
		(x, m) = list(map(int, ip.split()))
		h = 1
		mo = 1
		while h < x:
			h = h * 2
			mo += 1
		if mo > m:
			print(0)
		else:
			print(1 + (m - mo))
except:
	pass


from math import log, ceil
tt = int(input())
for i in range(tt):
	(x, m) = tuple(map(int, input().split()))
	steps = ceil(log(x, 2)) + 1
	if steps > m:
		print(0)
	else:
		print(m - steps + 1)


import math
for t in range(int(input())):
	(n, m) = map(int, input().split())
	a = math.ceil(math.log2(n))
	if m < a:
		print(0)
	else:
		print(m - a)


import math
for _ in range(int(input())):
	(x, m) = map(int, input().split())
	operations = math.ceil(math.log(x, 2))
	if operations > m:
		print(0)
	elif operations <= m:
		print(m - operations)