Alice recently converted all the positive integers from 1 to 2^{N} - 1 (both inclusive) into binary strings and stored them in an array S.  Note that the binary strings do not have leading zeroes.  
While she was out, Bob sorted all the elements of S in lexicographical increasing order.

Let S_{i} denotes the i^{th} string in the sorted array.  
Alice defined a function F such that F(S_{i}) is equal to the count of 1 in the string S_{i}.  
For example, F(101) = 2 and F(1000) = 1.
 
Given a positive integer K, find the value of \sum_{i = 1}^K F(S_{i}). 

String P is lexicographically smaller than string Q if one of the following satisfies:
P is a prefix of Q and P \neq Q.
There exists an index i such that P_{i} < Q_{i} and for all j < i,  P_{j}=Q_{j}.

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

- The first line will contain an integer T - number of test cases. Then the test cases follow.
- The first and only line of each test case contains two integers N and K.

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

For each test case, output the value \sum_{i = 1}^K F(S_{i}). 

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

$1 ≤ T ≤ 3000$
$1 ≤ N ≤ 50$
$1 ≤ K ≤ 2^{N} - 1$
- Sum of $N$ over all test cases does not exceed $10^{5}$.

----- Sample Input 1 ------ 
3
3 2
3 4
3 7
----- Sample Output 1 ------ 
2
5
12

----- explanation 1 ------ 
Converting positive integers to Binary Strings:
- $1 = 1$
- $2 = 10$
- $3 = 11$
- $4 = 100$
- $5 = 101$
- $6 = 110$
- $7 = 111$

Sorting Binary Strings in lexicographical order:
After sorting, the strings will appear in the following order:  
$[1, 10, 100, 101, 11, 110, 111]$.

Test case $1$: $F(S_{1}) + F(S_{2}) = F(1) + F(10) = 1 + 1 = 2$.

Test case $2$: $F(S_{1}) + F(S_{2}) + F(S_{3}) + F(S_{4}) = F(1) + F(10) + F(100) + F(101) = 1 + 1 + 1 + 2 = 5$.

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Mathematics


Solutions:
z = [0 for _ in range(51)]
z[1] = 1
for i in range(2, 51):
	z[i] = 2 * z[i - 1] + 2 ** (i - 2)
b = [0 for i in range(51)]
for i in range(1, 51):
	b[i] = b[i - 1] + z[i]

def sol1(target, n):
	value = 1
	sum1 = 1
	num1 = 1
	abnum = 2 ** (n - 1) - 1
	while value != target:
		if value + abnum > target:
			value = value + 1
			sum1 = sum1 + num1
			n = n - 1
			abnum = 2 ** (n - 1) - 1
		elif value + abnum < target:
			value = value + abnum + 1
			sum1 = sum1 + num1 * abnum
			n = n - 1
			for u in range(1, n):
				sum1 = sum1 + b[u]
			num1 = num1 + 1
			sum1 = sum1 + num1
			abnum = 2 ** (n - 1) - 1
		else:
			value = value + abnum
			sum1 = sum1 + num1 * abnum
			n = n - 1
			for u in range(1, n):
				sum1 = sum1 + b[u]
	return sum1
w = int(input())
for _ in range(w):
	(n, k) = list(map(int, input().strip().split()))
	print(sol1(k, n))


dp = [[0, 0], [2, 1]]
out = 0

def count(k, n, s):
	global out
	if k <= 0 or n <= 0:
		return
	if s:
		out += k
	if k == 1:
		return
	if k - (1 << n - 1) == 0:
		out += dp[n - 2][1]
		return
	if k - (1 << n - 1) < 0:
		count(k - 1, n - 1, 0)
		return
	out += dp[n - 2][1]
	count(k - (1 << n - 1), n - 1, 1)

def solve():
	global out
	(n, k) = [int(i) for i in input().split()]
	while len(dp) < n - 1:
		x = dp[-1]
		dp.append([x[0] * 2 + 2, 2 * x[1] + x[0] + 1])
	out = 0
	count(k, n, 1)
	print(out)
t = int(input())
for i in range(t):
	solve()


a = [0 for _ in range(51)]
a[1] = 1
for i in range(2, 51):
	a[i] = 2 * a[i - 1] + 2 ** (i - 2)
b = [0 for i in range(51)]
for i in range(1, 51):
	b[i] = b[i - 1] + a[i]

def sol(target, n):
	value = 1
	sum1 = 1
	num1 = 1
	abnum = 2 ** (n - 1) - 1
	while value != target:
		if value + abnum > target:
			value = value + 1
			sum1 = sum1 + num1
			n = n - 1
			abnum = 2 ** (n - 1) - 1
		elif value + abnum < target:
			value = value + abnum + 1
			sum1 = sum1 + num1 * abnum
			n = n - 1
			for u in range(1, n):
				sum1 = sum1 + b[u]
			num1 = num1 + 1
			sum1 = sum1 + num1
			abnum = 2 ** (n - 1) - 1
		else:
			value = value + abnum
			sum1 = sum1 + num1 * abnum
			n = n - 1
			for u in range(1, n):
				sum1 = sum1 + b[u]
	return sum1
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().strip().split()))
	print(sol(k, n))


import sys
MAX_DEPTH = 50

def build_lookup_table():
	table = [0 for _ in range(MAX_DEPTH)]
	for i in range(1, MAX_DEPTH):
		table[i] = 2 * table[i - 1] + 2 ** (i - 1)
	cumulative = [0 for _ in range(MAX_DEPTH)]
	for i in range(1, MAX_DEPTH):
		cumulative[i] = cumulative[i - 1] + table[i]
	return cumulative

def get_lexico_ordered_bits(n, k):
	ret = lexico_ordered_bits(n, k)
	return [1] + ret

def lexico_ordered_bits(n, k):
	if k <= 1:
		return []
	if k <= 2 ** (n - 1):
		return [0] + lexico_ordered_bits(n - 1, k - 1)
	else:
		return [1] + lexico_ordered_bits(n - 1, k - 2 ** (n - 1))

def solve(bits, n, i, lookup_table):
	level = n - len(bits) + (i + 1)
	if i == 0:
		if bits[i] == 1:
			child_count = 1
			ones_count = 1
			if level - 1 >= 0:
				child_count += 2 ** level - 1
				ones_count += lookup_table[level - 1]
			return (child_count, ones_count)
		else:
			return (1, 0)
	if bits[i] == 0:
		(child_count, ones_count) = solve(bits, n, i - 1, lookup_table)
		return (child_count + 1, ones_count)
	else:
		(child_count, ones_count) = solve(bits, n, i - 1, lookup_table)
		ones_count += child_count + 1
		child_count += 1
		if i == len(bits) - 1:
			return (child_count, ones_count)
		child_count += 2 ** level - 1
		if level - 1 >= 0:
			ones_count += lookup_table[level - 1]
		return (child_count, ones_count)
lookup_table = build_lookup_table()
t = int(sys.stdin.readline())
for _ in range(t):
	(n, k) = map(int, sys.stdin.readline().split())
	bits_k = get_lexico_ordered_bits(n, k)
	bits_k.reverse()
	if k == 1:
		print(1)
	else:
		print(solve(bits_k, n, len(bits_k) - 1, lookup_table)[1])


def func(n, k, toggle):
	if k == 2 ** n - 1:
		return n * 2 ** (n - 1) - (toggle ^ 1) * k * 1
	if n == 1:
		return toggle
	if k <= 2 ** n // 2:
		return toggle * k * 1 + func(n - 1, k - 1, 0)
	else:
		return toggle * k * 1 + func(n - 1, 2 ** (n - 1) - 1, 0) + func(n - 1, k - 2 ** n // 2, 1)
for case in range(int(input())):
	(N, K) = map(int, input().split())
	print(func(N, K, 1))


T = int(input())
for line in range(T):
	(N, K) = map(int, input().split())
	digits = [1]
	prior = [K - 1]
	counter = K
	block = 2 ** N - 1
	for d in range(1, N):
		if counter == 1:
			break
		counter -= 1
		block = (block + 1) // 2 - 1
		if counter <= block:
			digits.append(0)
			prior.append(0)
			continue
		counter -= block
		digits.append(1)
		prior.append(counter - 1)
	tally = K - 1
	for i in range(1, min(len(digits), N - 1)):
		d = digits[i]
		if d == 1:
			tally += (N - i - 2) * 2 ** (N - i - 1) + 1
			tally += prior[i]
	tally += sum(digits)
	print(tally)


from sys import stdin, stdout
import math
mod = 1000000007
mod9 = 998244353
fact = []

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def largePower(a, b, MOD):
	b = str(b)
	remainderB = 0
	for i in range(len(b)):
		remainderB = (remainderB * 10 + ord(b[i]) - 48) % (MOD - 1)
	return power(a, remainderB, MOD)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def binaryToDecimal(n):
	return int(n, 2)

def buildFact(n, m):
	fact.append(1)
	for i in range(1, n + 1):
		fact.append(fact[-1] * i)
		fact[-1] %= m
	return fact

def buildSieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p]:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def findDivisors(n):
	i = 1
	arr = []
	while i * i < n:
		if n % i == 0:
			arr.append(i)
		i += 1
	m = int(math.sqrt(n))
	for i in range(m, 0, -1):
		if n % i == 0:
			arr.append(n // i)

def solve():
	(n, k) = map(int, stdin.readline().split())
	arr = []
	if k <= n:
		print(k)
		return
	arr.append([2, 1])
	for i in range(n - 2):
		arr.append([2 + 2 * arr[-1][0] + arr[-1][1], 2 * arr[-1][1] + 1])
	i = 0
	k -= n
	ans = n
	while k >= arr[i][1]:
		ans += arr[i][0]
		i += 1
		k -= arr[i - 1][1]
		if k == 0:
			print(ans)
			return
	while k > 0:
		while k - 1 < arr[i][1] // 2:
			k -= 1
			ans += 2
			i -= 1
			if k == 0:
				print(ans)
				return
		i -= 1
		ans += arr[i][0]
		k -= arr[i][1]
		k -= 1
		ans += 2
		ans += k
	print(ans)
	return
tests = int(stdin.readline())
for _ in range(tests):
	solve()


def value(N, k):
	if k == 1:
		return 1
	elif k <= 2 ** (N - 1):
		return value(N - 1, k - 1)
	else:
		return value(N - 1, k - 2 ** (N - 1)) + 1

def sumk(N, k):
	if k == 1:
		return 1
	elif k <= 2 ** (N - 1):
		return 1 + sumk(N - 1, k - 1)
	else:
		return 1 + (N - 1) * 2 ** (N - 2) + (k - 2 ** (N - 1)) + sumk(N - 1, k - 2 ** (N - 1))
T = int(input())
for i in range(T):
	(N, K) = map(int, input().split(' '))
	print(sumk(N, K))


def solve(n, k):
	answer = 0
	level = 0
	curr = n
	while True:
		if k <= curr:
			answer += (level + 1) * k
			return answer
		answer += (level + 1) * curr
		k -= curr
		i = 1
		while k >= 2 ** i - 1:
			k -= 2 ** i - 1
			answer += (level + 1) * (2 ** i - 1) + sol[i]
			i += 1
		if k == 0:
			return answer
		level += 1
		curr = i
sol = [1, 1]
for i in range(2, 51):
	x = i - 1
	for j in range(len(sol)):
		x += 2 ** j - 1 + sol[j]
	sol.append(x)
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(solve(n, k))


import math
no_test = int(input())
sol = []
d = {}
d[1] = 1

def dic(k):
	if k in d:
		return d[k]
	else:
		d[k] = 2 * dic(k - 1) + 1
		return d[k]

def fun(e, k):
	if k <= e:
		return k
	a = e
	s = e
	n = 0
	while s + dic(n + 1) <= k:
		n += 1
		a += dic(n) + n * 2 ** (n - 1)
		s += dic(n)
	if k == s:
		return a
	a += k - s + fun(n + 1, k - s)
	return a
for _ in range(0, no_test):
	(a, b) = [int(x) for x in input().split()]
	sol.append(fun(a, b))
for k in sol:
	print(k)


def fullcount(k, n):
	pow2 = pow(2, n)
	if k <= 0:
		return 0
	if k == 2 * pow2 - 3:
		return (n - 1) * pow2 + 1
	if k < pow2 - 1:
		return fullcount(k - 1, n - 1)
	if k >= pow2 - 1:
		return fullcount(k - pow2, n - 1) + (k - pow2 + 2) + (n - 2) * pow2 // 2 + 1
	return 1 / 0
t = int(input())
for i in range(t):
	c = input().split()
	n = int(c[0])
	k = int(c[1])
	print(k + fullcount(k - 2, n - 1))