Let f(X) denote the number of set bits in X.

Given integers N and K, construct an array A of length N such that:
0 ≤ A_{i} ≤ K for all (1 ≤ i ≤ N);
\sum_{i=1}^{N} A_{i} = K

Over all such possible arrays, find the maximum value of \sum_{i=1}^{N} f(A_{i}).

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

- The first line of input contains a single integer T - the number of test cases. The description of T test cases follow.
- The only line of each test case contains integers N and K- the length of the array and sum of elements respectively.

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

For each test case, output the maximum value of \sum_{i=1}^{N} f(A_{i}).

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{9}$
$0 ≤ K ≤ 10^{9}$

----- Sample Input 1 ------ 
2
1 7
3 6

----- Sample Output 1 ------ 
3
4

----- explanation 1 ------ 
Test case $1$: Only one array is possible that is $A =[7]$. As $7 = (111)_2$, the number of set bits in $7$ is $3$. Thus, $\sum_{i=1}^{N} f(A_{i}) = f(7) = 3$.

Test case $2$: A possible array satisfying all the conditions is $A =[3, 0, 3]$. As $3 = (11)_2$, the number of set bits in $3$ is $2$. Similarly, the number of set bits in $0$ is $0$. Thus, $\sum_{i=1}^{N} f(A_{i}) = f(3) + f(0) + f(3) = 4$. It can be proven that answer never exceeds $4$.

Source: codechef | Difficulty: HARD
Tags: Mathematics

Implementation

Greedy algorithms


Solutions:
import sys
tcs = 1
tcs = int(input())
for tc in range(tcs):
	(n, k) = list(map(int, input().split()))
	if n == 1:
		print(bin(k)[2:].count('1'))
	else:
		ans = i = 0
		bit = flg = 1
		while flg:
			if k >= (1 << i) * n:
				ans += n
				k -= (1 << i) * n
				flg = 1
			else:
				cnt = k // (1 << i)
				k -= cnt * (1 << i)
				ans += cnt
				if k:
					k = (1 << i) - k
					for j in range(31):
						if 1 << j & k:
							ans -= 1
					ans += 1
				flg = 0
			i += 1
		print(ans)


import math
for i in range(int(input())):
	(n, k) = map(int, input().split())
	if k <= n:
		print(k)
	elif n == 1:
		b = bin(k)
		c = b.count('1')
		print(c)
	else:
		a = []
		i = 2
		t = 0
		while True:
			a.append(i - 1)
			if (i - 1) * (n - 1) > k:
				i //= 2
				break
			i *= 2
		b = math.log(i, 2)
		t += (n - 1) * b
		l = k - (i - 1) * (n - 1)
		if l in a:
			t += math.log(l + 1, 2)
		else:
			j = l // i
			t += j
			l = l % i
			j = bin(l)
			t += j.count('1')
		print(int(t))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	bit = bin(k)[:1:-1]
	(pos, ans, cnt, m) = ([], 0, 0, len(bit))
	for i in range(m - 1):
		temp = n + cnt
		flag = not int(bit[i]) and temp % 2 or (int(bit[i]) and (not temp % 2))
		ans += n - flag
		pos.append(n - flag)
		cnt = (temp - flag) // 2
	if not cnt and bit[-1] == '1':
		ans += 1
	elif cnt > 1:
		cnt = (cnt - 1) * 2
		for i in range(m - 2, -1, -1):
			if cnt <= pos[i]:
				ans -= cnt
				break
			ans -= pos[i]
			cnt = (cnt - pos[i]) * 2
	print(ans)


def setBits(n):
	if n == 0:
		return 0
	count = 1
	while True:
		n = n & n - 1
		if n != 0:
			count += 1
		else:
			break
	return count
arr = []

def precomputation():
	for i in range(33):
		temp = 1 << i
		temp -= 1
		arr.append(temp)

def solve():
	(n, k) = map(int, input().split())
	i = 0
	while arr[i] * n < k:
		i += 1
	(a, b) = (arr[i], arr[i - 1])
	(seta, setb) = (i, i - 1)
	upper = k - n * b
	lower = a - b
	x = upper // lower
	if upper % lower != 0:
		x += 1
	y = n - x
	ans = x * seta + y * setb
	z = x * a + y * b - k
	ans -= setBits(z)
	return ans
for _ in range(int(input())):
	precomputation()
	print(solve())


from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	i = 1
	while n * ((1 << i) - 1) < k:
		i += 1
	(a, b) = (1 << i - 1, 1 << i)
	y = ceil((k - n * (a - 1)) / a)
	x = n - y
	su = (a - 1) * x + (b - 1) * y
	print((i - 1) * x + i * y - bin(su - k).count('1'))


strng = lambda : input()
inp = lambda : int(input())
mul = lambda : map(int, input().split())
jn = lambda x, l: x.join(map(str, l))
strlst = lambda : list(input())
lst = lambda : list(map(int, input().split()))
dd = lambda : defaultdict(lambda : 0)
from collections import defaultdict
from math import ceil, log, floor, sqrt, gcd, log10
for _ in range(inp()):
	(n, k) = mul()
	i = 1
	while True:
		if (2 ** i - 1) * n <= k:
			i += 1
		else:
			i -= 1
			break
	rem = k - n * (2 ** i - 1)
	e = rem // 2 ** i
	ans = (n - 1) * i + e
	change = bin(rem % 2 ** i + 2 ** i - 1)
	print(ans + change.count('1'))


test = int(input())
while test:
	(n, k) = map(int, input().split())
	i = 1
	while True:
		if (2 ** i - 1) * n <= k:
			i += 1
		else:
			i -= 1
			break
	rem = k - n * (2 ** i - 1)
	extra_1 = rem // 2 ** i
	ans = n * i + extra_1
	change = bin(rem % 2 ** i + 2 ** i - 1)
	print(ans - i + change.count('1'))
	test -= 1


t = int(input())
while t > 0:
	t = t - 1
	s = input().split()
	n = int(s[0])
	k = int(s[1])
	ans = 0
	while k > 0:
		if k <= n:
			ans = ans + k
			k = 0
		else:
			diff = k - n
			if diff % 2 == 0:
				ans = ans + n
				k = diff // 2
			else:
				ans = ans + n - 1
				k = (diff + 1) // 2
	print(ans)


import math

def listp2(n):
	l = []
	while n > 0:
		t = 2 ** int(math.log(n, 2))
		n -= t
		l.append(t)
	return len(l)

def solve(n, k):
	if n >= k:
		return k
	if k == 0:
		return 0
	if n == 1:
		return listp2(k)
	cpow = 1
	csb = 1
	ans = 0
	while k > 0:
		nbr = k // cpow
		if nbr > n:
			ans += n
			k -= cpow * n
			cpow *= 2
			csb += 1
		else:
			ans += nbr
			rm = k % cpow
			(scp, spp) = (listp2(2 * cpow - 1 + rm), listp2(cpow - 1 + rm))
			if 0 < nbr < n:
				if scp + csb - 1 >= spp + csb:
					ans -= csb
					ans += scp
				else:
					ans -= csb - 1
					ans += spp
			elif nbr == 0:
				ans -= csb - 1
				ans += spp
			else:
				ans -= csb
				ans += scp
			k = 0
	return ans
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(solve(n, k))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	f = True
	res = 0
	j = 0
	while f:
		if k >= (1 << j) * n:
			res += n
			k -= (1 << j) * n
		else:
			z = k // (1 << j)
			k -= z * (1 << j)
			res += z
			if k:
				k = (1 << j) - k
				for i in range(31):
					if 1 << i & k:
						res -= 1
				res += 1
			f = False
		j += 1
	print(res)


import math
for i in range(int(input())):
	(n, k) = map(int, input().split())
	count = 0
	i = 0
	last = 0
	while k:
		if n * 2 ** i <= k:
			k -= n * 2 ** i
			count += n
			last += 2 ** i
		else:
			count += k // 2 ** i
			k -= k // 2 ** i * 2 ** i
			if k:
				count -= math.log2(last + 1)
				count += bin(last + k).count('1')
				k = 0
		i += 1
	print(int(count))


import sys
out = []
t = int(input())
for test in range(t):
	n_k = list(map(int, input().split()))
	n = n_k[0]
	k = n_k[1]
	power = 0
	f = 0
	count_ones_of_filled_mini = 0
	while k > 0:
		while k >= 2 ** power:
			num_slots = min(k // 2 ** power, n)
			if num_slots == n:
				count_ones_of_filled_mini += 1
			f += num_slots
			k -= num_slots * 2 ** power
			power += 1
		if k > 0:
			k += 2 ** power - 1
			f += bin(k)[2:].count('1') - count_ones_of_filled_mini
			k = 0
	out.append(str(f))
sys.stdout.write('\n'.join(out))


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

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

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		(n, k) = sep()
		if n == 1:
			print(bin(k).count('1'))
			continue
		if n >= k:
			print(k)
			continue
		ans = n
		k -= n
		j = 1
		while k:
			if k >= 2 ** j * n:
				k -= 2 ** j * n
				j += 1
				ans += n
			else:
				tot = k // 2 ** j
				ans += tot
				k = k % 2 ** j
				a = 2 ** j - 1
				a += k
				ans += bin(a).count('1') - j
				break
		print(ans)
main()


testCases = int(input())
while testCases > 0:
	testCases -= 1
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	ans = 0
	power = 1
	while k > 0:
		if k > n:
			if k % 2 == n % 2:
				k -= n
				ans += n
			else:
				k -= n - 1
				ans += n - 1
		else:
			ans += k
			break
		k //= 2
	print(ans)


n = int(input())
for _ in range(n):
	(N, x) = map(int, input().split())
	ans = 0
	while x:
		cur = min(x, N)
		if cur & 1 != x & 1:
			cur -= 1
		ans += cur
		x = (x - cur) // 2
	print(int(ans))


import math
t = int(input())
for k in range(t):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	if n >= k:
		print(k)
	else:
		ones = 0
		while True:
			if math.floor(k / (2 ** (ones + 1) - 1)) < n:
				break
			ones += 1
		ost = k - (2 ** ones - 1) * n
		dist = 2 ** (ones + 1) - 2 ** ones
		cnt = math.floor(ost / dist)
		ost2 = ost - cnt * dist
		end = ost2 + (2 ** ones - 1)
		cnt_bits = bin(end).count('1')
		print(cnt * (ones + 1) + (n - cnt - 1) * ones + cnt_bits)


t = int(input())
while t:
	t -= 1
	(n, k) = list(map(int, input().split()))
	(res, cnt) = (0, 0)
	for _ in range(31):
		if k % 2 == n % 2:
			cnt = n
		else:
			cnt = n - 1
		res += min(cnt, k)
		k -= min(cnt, k)
		k //= 2
	print(res)


import sys
import math
from collections import defaultdict, Counter, deque
from bisect import *
from string import ascii_lowercase
from heapq import *

def readInts():
	x = list(map(int, sys.stdin.readline().rstrip().split()))
	return x[0] if len(x) == 1 else x

def readList(type=int):
	x = sys.stdin.readline()
	x = list(map(type, x.rstrip('\n\r').split()))
	return x

def readStr():
	x = sys.stdin.readline().rstrip('\r\n')
	return x
write = sys.stdout.write
read = sys.stdin.readline
MAXN = 1123456

def dist(x1, x2, y1, y2):
	return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

def mergeSort(arr, check=lambda a, b: a < b, reverse=False):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		mergeSort(L, check, reverse)
		mergeSort(R, check, reverse)
		i = j = k = 0
		while i < len(L) and j < len(R):
			if check(L[i], R[j]):
				if not reverse:
					arr[k] = L[i]
					i += 1
				else:
					arr[k] = R[j]
					j += 1
			elif not reverse:
				arr[k] = R[j]
				j += 1
			else:
				arr[k] = L[i]
				i += 1
			k += 1
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1

def maxSum(arr, k):
	max_sum = 0
	max_cur = 0
	for (i, num) in enumerate(arr):
		max_cur = max(max_cur + num, num)
		if max_cur > max_sum:
			max_sum = max_cur
	return max_sum

def lcm(a, b):
	return a * b // math.gcd(a, b)

def get_power(n, m):
	i = 1
	p = 0
	while i <= n:
		i = i * m
		p += 1
	return p

def fact(n):
	f = 1
	for i in range(2, n + 1):
		f *= i
	return f

def find_closest(num, ar):
	min_d = float('inf')
	for num2 in ar:
		d = abs(num2 - num)
		if d < min_d:
			min_d = d
	return min_d

def check_pal(n):
	s = str(n)
	j = len(s) - 1
	i = 0
	while j > i:
		if s[i] != s[j]:
			return False
		i += 1
		j -= 1
	return True

def get_primes():
	primes = [False for _ in range(MAXN + 1)]
	used = [False for _ in range(MAXN + 1)]
	for i in range(2, MAXN + 1):
		if not used[i]:
			primes[i] = True
			for j in range(i, MAXN + 1, i):
				used[j] = True
	return primes

def isPrime(primes, n):
	if primes[n]:
		return True
	return False

def solve(t, primes=None):
	(k, n) = readInts()
	res = 0
	cur = 1
	while n > 0:
		nxt = max(n - k * cur, 0)
		if nxt != 0:
			rem = nxt % (cur * 2)
			if rem == 0:
				rem = cur * 2
			nxt = max(nxt, nxt + (cur * 2 - rem))
		plc = (n - nxt) // cur
		res += plc
		n = nxt
		cur *= 2
	print(res)

def main():
	t = 1
	t = readInts()
	for i in range(t):
		solve(i + 1)
main()


import math
for i in range(int(input())):
	(n, m) = map(int, input().split())
	if m <= n:
		print(m)
	elif n == 1:
		a = bin(m)[2:].count('1')
		print(a)
	else:
		d = 0
		ans = 0
		while m != 0:
			if n * 2 ** d <= m:
				ans += n
				m -= n * 2 ** d
				d += 1
			else:
				ans += m // 2 ** d
				m = m % 2 ** d
				ans -= d
				h = m
				m = 0
				for j in range(d):
					h += 2 ** j
				ans += bin(h).count('1')
		print(ans)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	ans = 0
	i = 0
	while True:
		if k >= (1 << i) * n:
			ans += n
			k -= (1 << i) * n
		else:
			temp = k // (1 << i)
			k -= temp * (1 << i)
			ans += temp
			if k:
				k = (1 << i) - k
				for j in range(31):
					if 1 << j & k:
						ans -= 1
				ans += 1
			break
		i += 1
	print(ans)


def isPalindrome(s):
	i = 0
	j = len(s) - 1
	while i < j:
		if s[i] != s[j]:
			return False
		i += 1
		j -= 1
	return True

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

def StrList():
	s = input()
	lis = [val for val in s]
	return lis

def FloatList():
	lis = input().split()
	lis = list(map(float, lis))
	return lis

def searchRange(nums, target):
	res = []
	ans1 = -1
	ans2 = -1

	def bs(nums, key):
		start = 0
		end = len(nums) - 1
		ans = -1
		while start <= end:
			mid = start + (end - start) // 2
			if nums[mid] == key:
				ans = mid
				end = mid - 1
			elif nums[mid] > key:
				end = mid - 1
			else:
				start = mid + 1
		return ans

	def bs1(nums, key):
		start = 0
		end = len(nums) - 1
		ans = -1
		while start <= end:
			mid = start + (end - start) // 2
			if nums[mid] == key:
				ans = mid
				start = mid + 1
			elif nums[mid] > key:
				end = mid - 1
			else:
				start = mid + 1
		return ans
	ans1 = bs(nums, target)
	ans2 = bs1(nums, target)
	res.append(ans1)
	res.append(ans2)
	return res

def SieveOfEratosthenes(n, isPrime):
	isPrime[0] = isPrime[1] = False
	for i in range(2, n + 1):
		isPrime[i] = True
	p = 2
	while p * p <= n:
		if isPrime[p] == True:
			i = p * p
			while i <= n:
				isPrime[i] = False
				i += p
		p += 1

def findPrimePair(n):
	isPrime = [0] * (n + 1)
	SieveOfEratosthenes(n, isPrime)
	for i in range(0, n):
		if isPrime[i] and isPrime[n - i]:
			print(i, n - i)
			return

def solveByPRateek():
	(n, k) = map(int, input().split())
	if n == 1:
		i = 0
		a = 1 << i
		while a < k:
			i += 1
			a = 1 << i
			a -= 1
		print(i)
		return
	if n >= k:
		print(k)
		return
	result = 0
	check = True
	i = 0
	while check:
		if k >= (1 << i) * n:
			result += n
			k -= (1 << i) * n
			check = True
		else:
			cnt = k // (1 << i)
			k -= cnt * (1 << i)
			result += cnt
			if k:
				k = (1 << i) - k
				for j in range(32):
					if 1 << j & k:
						result -= 1
				result += 1
			check = False
		i += 1
	print(result)
tt = int(input())
while tt:
	tt -= 1
	solveByPRateek()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	result = 0
	bit = 1
	check = True
	i = 0
	while check:
		if k >= (1 << i) * n:
			result += n
			k -= (1 << i) * n
			check = True
		else:
			cnt = k // (1 << i)
			k -= cnt * (1 << i)
			result += cnt
			if k:
				k = (1 << i) - k
				for j in range(31):
					if 1 << j & k:
						result -= 1
				result += 1
			check = False
		i += 1
	print(result)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	ans = 0
	b = 1
	flag = True
	i = 0
	while flag:
		if k >= (1 << i) * n:
			ans += n
			k -= (1 << i) * n
			flag = True
		else:
			count = k // (1 << i)
			k -= count * (1 << i)
			ans += count
			if k:
				k = (1 << i) - k
				for j in range(31):
					if 1 << j & k:
						ans -= 1
				ans += 1
			flag = False
		i += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	NoOfBits = 0
	f = True
	i = 0
	while f:
		if k >= (1 << i) * n:
			NoOfBits += n
			k -= (1 << i) * n
			f = True
		else:
			count = k // (1 << i)
			k -= count * (1 << i)
			NoOfBits += count
			if k:
				k = (1 << i) - k
				for j in range(31):
					if 1 << j & k:
						NoOfBits -= 1
				NoOfBits += 1
			f = False
		i += 1
	print(NoOfBits)


from math import gcd
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	i = 0
	while True:
		if k >= (1 << i) * n:
			ans += n
			k -= (1 << i) * n
		else:
			ct = k // (1 << i)
			k -= ct * (1 << i)
			ans += ct
			if k:
				k = (1 << i) - k
				for j in range(31):
					if 1 << j & k:
						ans -= 1
				ans += 1
			break
		i += 1
	print(ans)


for i in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	indices = [0] * 35
	s = str(bin(k))
	for i in range(1, len(s) - 1):
		if s[-i] == '1':
			indices[-i] = 1
	for j in range(len(indices)):
		for i in range(len(indices) - 1):
			if indices[i] == 0:
				continue
			elif indices[i] * 2 + indices[i + 1] <= n:
				indices[i + 1] += indices[i] * 2
				indices[i] = 0
			else:
				temp = (n - indices[i + 1]) // 2
				indices[i] -= temp
				indices[i + 1] += temp * 2
	print(sum(indices))


from sys import stdin
input = stdin.readline

def solve(N, K):
	count = 0
	index = 0
	while count + N * 2 ** index <= K:
		count += N * 2 ** index
		index += 1
	if count == K:
		return N * index
	x = (K - count) // 2 ** index
	if count + x * 2 ** index == K:
		return N * index + x
	excess = (x + 1) * 2 ** index - (K - count)
	excess = [int(b) for b in bin(excess)[2:]]
	return N * index + x + 1 - sum(excess)
T = int(input().strip())
for problem in range(1, T + 1):
	(N, K) = [int(x) for x in input().strip().split()]
	print(solve(N, K))


for t in range(int(input())):
	(n, k) = map(int, input().split())
	z = 0
	while k > 0:
		t = min(n, k)
		if k - t & 1:
			t -= 1
		z += t
		k -= t
		k //= 2
	print(z)


import math
for iota in range(int(input())):
	(n, k) = tuple(map(int, input().split()))
	if n == 1:
		print(bin(k).count('1'))
		continue
	if n >= k:
		print(k)
		continue
	i = 1
	val = 1
	summ = n * val
	ans = n
	while True:
		if summ == k:
			break
		val += pow(2, i)
		if n * val <= k:
			ans += n
			summ = n * val
		else:
			tries = (k - summ) / pow(2, i)
			ans += int(tries)
			if int(tries) != tries:
				toadd = k - summ - int(tries) * pow(2, i)
				ans -= i
				ans += bin(val + toadd - pow(2, i)).count('1')
				summ = k
				continue
			summ = k
		i += 1
	print(ans)


import sys
sys.setrecursionlimit(1000000)

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

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())

def printyes():
	print('YES')

def printno():
	print('NO')

def f(n):
	count = 0
	while n:
		count += n & 1
		n >>= 1
	return count
for t in range(int(input())):
	(n, k) = mi()
	i = 0
	count = 0
	for i in range(32):
		maxcount = k // 2 ** i
		if maxcount > n:
			k -= n * 2 ** i
			count += n
		else:
			k -= maxcount * 2 ** i
			count += maxcount
			if k > 0:
				count -= f(2 ** i - 1)
				count += f(2 ** i - 1 + k)
			break
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = i = 0
	while 1:
		if k >= (1 << i) * n:
			a += n
			k -= (1 << i) * n
		else:
			mi = k // (1 << i)
			k -= mi * (1 << i)
			a += mi
			if k:
				k = (1 << i) - k
				for j in range(31):
					if 1 << j & k:
						a -= 1
				a += 1
			break
		i += 1
	print(a)


import math

def ffind(a, n):
	c = 0
	while n > 0:
		if n % 2 == 1:
			c += 1
		n = n // 2
	return a + c
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n >= k:
		print(min(n, k))
	else:
		a = 1
		c = 0
		if n < 2:
			print(ffind(0, k))
		else:
			while k >= (n - 1) * a:
				k = k - (n - 1) * a
				c = c + (n - 1)
				a = a * 2
			aa = k // a
			ans = c + aa + ffind(0, k - a * aa)
			print(ans)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	li = []
	i = 1
	while i <= k:
		li.append(i - 1)
		i *= 2
	if i - 1 == k:
		li.append(k)
	if k <= n:
		print(k)
	elif n == 1:
		bits = 0
		while k:
			if k & 1:
				bits += 1
			k = k >> 1
		print(bits)
	else:
		va = -1
		for w in li:
			if w * n >= k:
				va = w
				break
		bits = n * li.index(va)
		su = va * n
		diff = va - li[li.index(va) - 1]
		diff1 = su - k
		mod = diff1 // diff
		bits -= mod
		if diff1 % diff != 0:
			diff = diff1 - mod * diff
			bits -= li.index(va)
			(c, v) = (0, va - diff)
			while v:
				if v & 1:
					c += 1
				v = v >> 1
			bits += c
		print(bits)


from math import log2
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	if n == 1:
		print(list(bin(k)[2:]).count('1'))
	elif k <= n:
		print(k)
	else:
		ans = n
		k -= n
		(bit, occr) = (2, k // 2)
		(mx_bit, mx_bit_occr) = (0, 0)
		while occr:
			if occr > n:
				occr = n
			(mx_bit, mx_bit_occr) = (bit, occr)
			k -= occr * bit
			ans += occr
			bit *= 2
			occr = k // bit
		nxt_emp_cnt = n - mx_bit_occr
		if k == 0:
			print(ans)
		else:
			while k < bit:
				bit = bit // 2
			while k != 0:
				occr = k // bit
				(l1, l2) = (log2(mx_bit) - 1, log2(bit))
				ans -= int(l1 - l2) * occr
				k -= occr * bit
				mx_bit = bit
				if k == 0:
					break
				while k < bit:
					bit = bit // 2
			print(ans)


t = int(input())
for T in range(t):
	(n, k) = map(int, input().split())
	if n >= k:
		print(k)
	else:
		mx = 1
		mn = 1
		ans = n
		i = 2
		k -= n
		q = 0
		while k >= i:
			if k >= i * n:
				al = n
				mx += i
				mn = mx
			else:
				al = k // i
				q = n - al
				mx += i
			ans += al
			k -= al * i
			i *= 2
		el = 0
		i //= 2
		c1 = 0
		c2 = 0
		mx1 = mx
		mn1 = mn
		u = k + mx1
		v = k + mn1
		while mx1:
			c1 += mx1 & 1
			mx1 >>= 1
		while mn1:
			c2 += mn1 & 1
			mn1 >>= 1
		c3 = 0
		c4 = 0
		while u:
			c3 += u & 1
			u >>= 1
		while v:
			c4 += v & 1
			v >>= 1
		ans = ans - min(c1 - c3, c2 - c4)
		print(ans)


from math import ceil, gcd, factorial, sqrt, log, log2, pi
import queue
import heapq as hq
from itertools import permutations, combinations, accumulate, product
from collections import Counter, deque
from bisect import bisect, insort, bisect_left, insort_left
from sys import stdin, stdout
input = stdin.readline

def sieve(n):
	prime = [True] * (n + 1)
	p = 2
	prime[0] = False
	prime[1] = False
	for p in range(2, int(n ** 0.5) + 1):
		if prime[p] == True:
			for l1 in range(p * p, n + 1, p):
				prime[l1] = False
	return prime

def simplesieve(n):
	prime = [2]
	mak = [False] * (n + 1)
	for p in range(3, n + 1, 2):
		if mak[p] == False:
			prime.append(p)
			if p * p <= n:
				for l1 in range(p * p, n + 1, 2 * p):
					mak[l1] = True
	return prime

def segementedsieve(low, high):
	primes = simplesieve(int(high ** 0.5))
	prime = [True] * (high - low + 1)
	for i in primes:
		lower = low // i * i
		if lower < low:
			lower += i
		for j in range(lower, high + 1, i):
			if j != i:
				prime[j - low] = False
	ans = []
	for i in range(low, high + 1):
		if prime[i - low]:
			ans.append(i)
	return ans

def isprime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n == 1:
		return False
	for l1 in range(3, int(n ** 0.5) + 1, 2):
		if n % l1 == 0:
			return False
	return True

def binpow(a, b, m):
	r2 = 1
	a = a % m
	while b > 0:
		if b & 1:
			r2 = r2 * a % m
		a = a * a % m
		b >>= 1
	return r2

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

def gcdExtended(a, b):
	if b == 0:
		return (a, 1, 0)
	(g, x1, y1) = gcdExtended(b, a % b)
	(x1, y1) = (y1, x1 - a // b * y1)
	return (g, x1, y1)

def binseach(a, l, r, key):
	while r - l > 1:
		m = l + (r - l) // 2
		if a[m] <= key:
			l = m
		else:
			r = m
	if a[l] == key:
		return l
	if a[r] == key:
		return r
	return -1

def inorder(root):
	(res, stack) = ([], [])
	current = root
	while True:
		while current:
			stack.append(current)
			current = current.left
		if len(stack) == 0:
			return res
		node = stack[-1]
		stack.pop(len(stack) - 1)
		if node.data != None:
			res.append(node.data)
		current = node.right
	return res

def find(n):
	if par[n] == n:
		return n
	par[n] = find(par[n])
	return par[n]

def union(a, b):
	a1 = find(a)
	b1 = find(b)
	if a1 != b1:
		if rank[a1] >= rank[b1]:
			par[b1] = a1
			rank[a1] += rank[b1]
		else:
			rank[b1] += rank[a1]
			par[a1] = b1

def dfs(s, p):
	v[s] = 1
	path.append(s)
	for i in a[s]:
		if v[i] == 0:
			if dfs(i):
				return True
		elif i != p:
			path.append(i)
			return True
	path.pop()
	return False

def bfs(graph, n, x, dest):
	v = [0] * (1 + n)
	d = [0] * (1 + n)
	d[x] = 0
	v[x] = 1
	q = queue.Queue()
	q.put(x)
	p = [0] * (1 + n)
	p[x] = -1
	while not q.empty():
		z = q.get()
		for s in graph[z]:
			if v[s] == 0:
				v[s] = 1
				d[s] = d[z] + 1
				q.put(s)
	return d[dest]
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n >= k:
		print(k)
		continue
	c = 0
	ans = 0
	if abs(k - n) % 2 == 0:
		while 1:
			if 2 ** c * n <= k:
				k = k - 2 ** c * n
			else:
				break
			c += 1
			ans += n
		ans += k // 2 ** c
		rem = k % 2 ** c
		rem = 2 ** c - rem
		if rem > 0:
			ans += 1
		for i in range(63, -1, -1):
			if rem & 1 << i:
				ans -= 1
		print(ans)
	else:
		k = k - (n - 1)
		c = 1
		ans = n - 1
		while 1:
			if 2 ** c * n <= k:
				k = k - 2 ** c * n
			else:
				break
			c += 1
			ans += n
		ans += k // 2 ** c
		rem = k % 2 ** c
		rem = 2 ** c - rem
		if rem > 0:
			ans += 1
		for i in range(63, -1, -1):
			if rem & 1 << i:
				ans -= 1
		print(ans)


for z in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	if n >= k:
		print(k)
	else:
		n = n - 1
		i = 1
		while k != 0:
			div = k // i
			if div == 0:
				break
			div = min(n, div)
			k -= div * i
			i *= 2
			ans += div
		print(ans + str(bin(k)[2:]).count('1'))


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	nsb = 0
	i = 0
	while True:
		tmp2 = 1 << i
		tmp = tmp2 * n
		if k >= tmp:
			nsb += n
			k -= tmp
		else:
			mdiff = k // tmp2
			k -= mdiff * tmp2
			nsb += mdiff
			if k:
				k = tmp2 - k
				for j in range(0, 31):
					if 1 << j & k:
						nsb -= 1
				nsb += 1
			break
		i += 1
	print(math.floor(nsb))


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	(val, ans) = (0, 0)
	for i in range(28):
		a = 1 << i
		if (val + a) * N == M:
			val += a
			i += 1
			break
		if (val + a) * N > M:
			break
		val += a
	M -= val * N
	ans += N * i
	B = M // (1 << i)
	M -= B * (1 << i)
	ans += B
	ans -= i
	C = bin(val + M)
	D = C[2:].count('1')
	ans += D
	print(ans)


from math import pow
for _ in range(int(input())):

	def countSetBits(n):
		count = 0
		while n:
			n &= n - 1
			count += 1
		return count
	ans = 0
	(n, k) = map(int, input().split())
	if n == 1:
		print(countSetBits(k))
	elif k <= n:
		print(k)
	else:
		ans = 0
		i = 0
		while n * (int(pow(2, i)) - 1) <= k:
			i += 1
		i -= 1
		ans = n * i
		x = int(pow(2, i))
		k = k - n * (int(pow(2, i)) - 1)
		z = k // x
		k -= z * x
		ans += z
		y = int(pow(2, i)) - 1
		ans -= i
		y += k
		ans += countSetBits(y)
		print(ans)


def cb(x):
	s = bin(x)
	ans = 0
	for i in s:
		if i == '1':
			ans += 1
	return ans
t = int(input())
for _ in range(t):
	a = list(map(int, input().split()))
	n: int = a[0]
	k = a[1]
	if n >= k:
		print(k)
	else:
		cd = 0
		i = 0
		ans = 0
		while k:
			if k >= n * 2 ** i:
				ans = ans + n
				cd = cd + 2 ** i
				k = k - n * 2 ** i
			else:
				ans += k // 2 ** i
				k = k - 2 ** i * (k // 2 ** i)
				break
			i += 1
		print(ans - cb(cd) + cb(k + cd))


def set_bits_in(num):
	count = 0
	while num > 0:
		if num & 1 == 1:
			count += 1
		num = num >> 1
	return count
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	ans = 0
	a = 1
	while k > 0:
		if k % (a * 2):
			c = min(k // a, n if n % 2 else n - 1)
			k = k - a * c
			ans += c
		else:
			c = min(k // a, n - 1 if n % 2 else n)
			k = k - a * c
			ans += c
		a = a * 2
	print(ans)


def ccc(n):
	count = 0
	while n:
		count += n & 1
		n >>= 1
	return count
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	c = n
	cnt = 0
	ans = 0
	cc = 0
	summ = 0
	while c > 1:
		cnt += 1
		c = c // 2
	for i in range(40):
		w = 2 ** i
		rem = k % w
		if summ + n * w <= k:
			summ += n * w
			ans += n
		else:
			diff = (k - summ) // w
			rem = (k - summ) % w
			ans += diff
			ans -= i
			q = 2 ** i - 1
			kk = q + rem
			j = ccc(kk)
			ans += j
			break
	print(ans)


def count_set_bits(num):
	count = 0
	while num > 0:
		count += num & 1
		num = num >> 1
	return count
nq = int(input())
for _ in range(nq):
	inp = list(input().split())
	n = int(inp[0])
	k = int(inp[1])
	k_1 = k
	i = 0
	count = 0
	a = []
	while 2 ** i <= k:
		tmp = k // 2 ** i
		tmp = min(tmp, n - 1)
		a.append(tmp)
		count += tmp
		k += -tmp * 2 ** i
		i += 1
	count += count_set_bits(k)
	print(count)


T = int(input())

def check(n):
	if n > 0:
		return n % 2 + check(n // 2)
	else:
		return 0
for _ in range(T):
	(N, K) = map(int, input().split())
	i = 1
	if K == 0:
		print(0)
		continue
	s = 0
	while K > 0:
		if K >= i * N:
			s += N
			K -= i * N
			i = i * 2
		else:
			s += K // i
			K -= K // i * i
			if check(i - 1) - check(i - 1 + K) >= check(i * 2 - 1) - check(i * 2 - 1 + K):
				s += check(i * 2 - 1 + K)
				s -= check(i * 2 - 1)
			else:
				s += check(i - 1 + K)
				s -= check(i - 1)
			K = 0
	print(s)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	ret = 0
	while K:
		num_bits_set = N
		if (N - K) % 2:
			num_bits_set -= 1
		if num_bits_set > K:
			num_bits_set -= (num_bits_set - K) // 2 * 2
		ret += num_bits_set
		K -= num_bits_set
		K //= 2
	print(ret)


tc = int(input())
for case in range(tc):
	(n, k) = map(int, input().split())
	ans = 0
	mod = 1
	mn = float('inf')
	while k >= mod:
		giv = k // mod
		if giv >= n:
			mn = mod
		ans += min(giv, n)
		k -= min(giv, n) * mod
		mod += mod
	if mn != float('inf'):
		x = (mn << 1) - 1
		cnt = bin(k + x)[2:].count('1') - bin(x)[2:].count('1')
		ans += cnt
	print(ans)


import math
for h in range(int(input())):
	(n, k) = map(int, input().split())
	c = 0
	i = 0
	while k > 0:
		if n * 2 ** i <= k:
			k -= n * 2 ** i
			c += n
		else:
			break
		i += 1
	c += k // 2 ** i
	k = k % 2 ** i
	if k != 0:
		c -= i
		c += 1
		k -= 1
		c += bin(k)[2:].count('1')
	print(c)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	start = 1
	k = x
	ans = 0
	while x:
		if start * n <= x:
			x -= start * n
			ans += n
		else:
			kitne = x // start
			ans += kitne
			x -= kitne * start
			if x:
				ans += 1 - str(bin(start - x)).count('1')
			x = 0
		start *= 2
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	i = 0
	last = k
	n -= 1
	while k > 0:
		pow = 1 << i
		i += 1
		minus = n * pow
		if minus <= k:
			ans += n
			k -= minus
		else:
			ans += k // pow
			k -= k // pow * pow
		if k == last:
			break
		last = k
	ans += bin(k)[2:].count('1')
	print(ans)


def solve():
	(n, k) = list(map(int, input().split()))
	bi = bin(k).replace('0b', '')
	bi = bi[::-1]
	arr = [int(i) for i in bi]
	rep = 0
	while rep < 30:
		i = len(bi) - 1
		while i >= 0:
			if arr[i] > 0:
				incr = 2 ** i
				for j in range(i):
					fit = incr // 2 ** j
					push = max(0, n - arr[j]) // fit
					we = min(arr[i], push)
					arr[j] += we * fit
					arr[i] -= we
					if arr[i] == 0:
						break
			i -= 1
		rep += 1
	print(sum(arr))
try:
	for tc in range(int(input())):
		solve()
except:
	pass


def setBitNumber(n):
	n |= n >> 1
	n |= n >> 2
	n |= n >> 4
	n |= n >> 8
	n |= n >> 16
	n = n + 1
	return n >> 1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 1:
		print(bin(k).count('1'))
	elif k < n:
		print(k)
	else:
		final = 0
		ans = setBitNumber(k // n)
		if k // n == ans * 2 - 1:
			ans = k // n
		else:
			ans -= 1
		reminder = k - ans * n
		temp = ans + 1
		x = reminder // temp
		reminder -= x * temp
		reminder += ans
		final = x + bin(reminder).count('1') + bin(ans).count('1') * (n - 1)
		print(final)


import math
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	if k <= n:
		ans = k
	else:
		ans = n
		k -= n
		i = 1
		j = 1
		while k > 0:
			if 2 * j * n <= k:
				ans += n
				k -= 2 * j * n
				j *= 2
				i += 1
			else:
				ans += k // (2 * j)
				k -= k // (2 * j) * (2 * j)
				a = 2 ** i - 1
				x = str(bin(a))
				a += k
				y = str(bin(a))
				ans += y.count('1') - x.count('1')
				k = 0
	print(ans)