Mathison has bought a new deck of cards that contains 2N cards, numbered and ordered from 0 to 2N-1.
Mathison is getting bored and decides to learn the Dynamo shuffle (or Sybil cut) - a flashy manner to shuffle cards. Unfortunately, the Dynamo shuffle is a little too complicated so Mathison decides to create his own shuffle.

This newly invented shuffle is done in N steps. At step k (0 ≤ k < N) the deck is divided into 2k equal-sized decks
where each one contains cards that lie on consecutive positions.
Each one of those decks is then reordered: all the cards that lie on even positions are placed first followed by all cards that lie on odd positions
(the order is preserved in each one of the two subsequences and all positions are 0-based). Then all the decks are put back together (preserving the order of decks).

Mathison has spent hours practising the shuffle and he now believes that he has perfected his technique. However, Chef doesn't believe him yet so he asks Mathison to answer Q questions that given a deck of size 2N where i-th card is labelled i, find the position of the card labelled K in the final, shuffled deck.

-----Input-----
The first line of the input file will contain one integer, Q, representing the number of Chef's questions.
Each of the next Q lines will contain a pair of integers, N and K.

-----Output-----
The output file will contain Q lines, each one representing the answer to one of Chef's questions.

-----Constraints-----
- 1 ≤ Q ≤ 1000
- 1 ≤ N ≤ 64
- 0 ≤ K < 2N

-----Subtaks-----
Subtask #1 (30 points):

- 1 ≤ N ≤ 10

Subtask #2 (30 points):

- 1 ≤ N ≤ 32

Subtask #3 (40 points):

- Original constraints

-----Example-----
Input:
3
3 4
3 3
3 2

Output:
1
6
2

Input:
1
64 11047805202224836936

Output:
1337369305470044825

-----Explanation-----
In all questions, we have N = 3. Therefore, we have a deck with 8 cards.
The shuffling is done in three steps:

Step 0: We divide {0, 1, 2, 3, 4, 5, 6, 7} in 20 decks. We get only one deck.
The deck is reordered into {0, 2, 4, 6, 1, 3, 5, 7}.

Step 1: We divide {0, 2, 4, 6, 1, 3, 5, 7} in 21 decks. We get two decks: {0, 2, 4, 6} and {1, 3, 5, 7}.
{0, 2, 4, 6} is reordered into {0, 4, 2, 6} while {1, 3, 5, 7} is reordered into {1, 5, 3, 7}.
We get {0, 4, 2, 6, 1, 5, 3, 7} when we put the decks back together.

Step 2: We divide {0, 4, 2, 6, 1, 5, 3, 7} in 22 decks. We get four decks: {0, 4}, {2, 6}, {1, 5} and {3, 7}.
Each one of the four decks stays the same after it is reordered (as there are only two elements to reorder).
We get the final, shuffled deck: {0, 4, 2, 6, 1, 5, 3, 7}.

The card labelled 4 is on position 1.
The card labelled 3 is on position 6.
The card labelled 2 is on position 2.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	mm = bin(k)[2:]
	if len(mm) != n:
		j = str(0) * (n - len(mm))
		mm = j + mm
	l = int(mm[::-1], 2)
	print(l)


def pos(po, n):
	if n == 0:
		return 0
	if po % 2 == 0:
		return 0 + pos(po // 2, n - 1)
	else:
		return 2 ** (n - 1) + pos(po // 2, n - 1)
t = int(input())
for te in range(t):
	(n, k) = list(map(int, input().split()))
	print(pos(k, n))


def fun():
	t = int(input())
	for a0 in range(t):
		(n, k) = map(int, input().strip().split())
		no = 2 ** n
		pre = 0
		for i in range(n):
			if k % 2 == 0:
				k = k // 2
			else:
				pre = pre + 2 ** (n - 1 - i)
				k = k - int(k // 2) - 1
		ans = pre + k
		print(ans)
fun()


from math import floor, log

def f(n, k):
	if k == 0:
		return 0
	if k == 1:
		return 2 ** (n - 1)
	return f(n, k - 2 ** floor(log(k, 2))) + 2 ** (n - floor(log(k, 2)) - 1)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(f(n, k))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = bin(k)[2:]
	a = str(a)
	a = a.zfill(n)
	a = a[::-1]
	print(int(a, 2))


T = int(input().strip())
for test in range(T):
	(N, K) = map(int, input().split())
	assert 1 <= N <= 64
	assert 0 <= K < 2 ** N
	bin_rep = bin(K)[2:]
	bin_rep = '0' * (N - len(bin_rep)) + bin_rep
	print(int(bin_rep[::-1], 2))


t = int(input())
for _ in range(t):
	(b, num) = map(int, input().split())
	k = 1
	sum = 0
	for i in range(b):
		if num & 1 << i:
			sum += 1 * (1 << b - 1 - i)
	print(sum)


t = int(input())
for z in range(t):
	(n, k) = map(int, input().split())
	pos = k
	tot = pow(2, n)
	ans = 0
	for i in range(n):
		if pos % 2 == 0:
			pos = pos // 2
		else:
			ans += tot // 2
			pos = pos // 2
		tot = tot // 2
	ans += pos
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	ans = 0
	for j in range(n - 1, -1, -1):
		if k % 2:
			ans += 1 << j
		k = k // 2
	print(ans + k)


n = int(input())
for i in range(0, n):
	(k, u) = map(int, input().split())
	count = 0
	for j in range(k - 1, -1, -1):
		if u % 2 == 1:
			count = count + (1 << j)
		u = u >> 1
	print(count)


t = int(input())
while t > 0:
	x = input().split()
	n = int(x[0])
	k = int(x[1])
	ans = 0
	for i in range(n):
		if k & 1 << i != 0:
			ans += 2 ** (n - i - 1)
	print(ans, end='\n')
	t -= 1


q = int(input())
for i in range(q):
	(n, k) = map(int, input().split(' '))
	index = k
	for j in range(n):
		y = j
		if j == 0:
			if k % 2 == 0:
				index = index // 2
			else:
				index = (index + (2 ** n - 1)) // 2
		else:
			m = 2 ** n // 2 ** j
			part = index // m + 1
			base = m * (part - 1)
			r = index - base
			if r % 2 == 0:
				index = base + r // 2
			else:
				index = base + (m + r - 1) // 2
	print(index)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	p = 0
	while n > 0:
		if k % 2 == 0:
			k = k // 2
		else:
			k = k + (2 ** n - k) // 2
		n = n - 1
		if k >= 2 ** n:
			k = k - 2 ** n
			p = p + 2 ** n
	print(int(p + k))
	t = t - 1


import math
t = int(input())
for i in range(t):
	(n, k) = input().split(' ')
	n = int(n)
	k = int(k)
	z = pow(2, n)
	p = 0
	q = z
	yo = k
	nt = n
	for i in range(1, n):
		if yo % 2 == 0:
			pp = pow(2, nt)
			xx = yo % pp
			yo = yo - xx // 2
		else:
			pp = pow(2, nt)
			xx = yo % pp
			xx = pow(2, nt) - xx - 1
			yo = yo + xx // 2
		nt = nt - 1
	print(yo)


import decimal
from decimal import Decimal
trial = int(input())
for i in range(trial):
	(n, k) = list(map(int, input().split()))
	a = int(Decimal(k) / 2)
	b = k % 2
	for i in range(n - 2, -1, -1):
		b = 2 * b + a % 2
		a = int(Decimal(a) / 2)
	print(b)


def pos(l, r, np):
	if l == r:
		return np
	p = np - l
	if p % 2 == 1:
		np = (l + r) // 2 + 1 + p // 2
		l = (l + r) // 2 + 1
	else:
		np = l + p // 2
		r = (l + r) // 2
	return pos(l, r, np)
t = int(input())
for _ in range(t):
	(n, k) = input().split(' ')
	n = int(n)
	k = int(k)
	print(int(pos(0, 2 ** n - 1, k)))


t = int(input())
for i in range(t):
	(n, k) = input().split(' ')
	(n, k) = (int(n), int(k))
	s = bin(k)
	s = s[2:]
	if len(s) == n:
		s = s[::-1]
		a = int(s, 2)
		print(a)
	else:
		p = n - len(s)
		for j in range(p):
			s = '0' + s
		s = s[::-1]
		a = int(s, 2)
		print(a)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	i = 1
	t = 0
	while i <= k:
		temp = i & k
		if temp:
			ans = ans | 1 << n - t - 1
		i *= 2
		t += 1
	print(ans)


q = int(input())
for i in range(q):
	(n, x) = map(int, input().split())
	su = 0
	j = 0
	for j in range(n):
		if x % 2 != 0:
			su += 2 ** (n - 1 - j)
			x = int(x // 2)
		else:
			x = int(x // 2)
	print(su)


t = int(input())
for cas in range(t):
	(n, k) = map(int, input().split())
	i = 0
	x = k
	pos = k
	nn = pow(2, n)
	while i < n:
		cur = nn // pow(2, i)
		tmp = pos % cur
		if tmp % 2 == 0:
			xl = tmp // 2
			z = pos // cur
			z *= cur
			pos = z + xl
		else:
			xl = cur // 2 + tmp // 2
			pos = pos + xl - tmp
		i += 1
	print(pos)


def find(N, k):

	def findout(N, i, k):
		if i == 0:
			return k
		else:
			num = k // 2 ** (N - i + 1)
			remain = k % 2 ** (N - i + 1)
			if remain <= 2 ** (N - i) - 1:
				remain *= 2
			else:
				remain -= 2 ** (N - i)
				remain *= 2
				remain += 1
			position = num * 2 ** (N - i + 1) + remain
			return findout(N, i - 1, position)
	return findout(N, N, k)
for _ in range(int(input())):
	A = list(map(int, input().strip().split(' ')))
	print(find(A[0], A[1]))


POWER = list()
POWER.append(1)
for i in range(0, 75):
	POWER.append(POWER[i] * 2)
q = int(input())
while q > 0:
	(n, k) = map(int, input().split())
	b = POWER[n - 1]
	x = k + 1
	pik = 1
	ret = 0
	while x != 1:
		if x > b:
			x = x - b
			ret = ret + pik
		b = b // 2
		pik = pik * 2
	print(ret)
	q = q - 1


tt = int(input())
while tt:
	(n, k) = input().split(' ')
	n = int(n)
	k = int(k)
	siz = pow(2, n)
	p = 0
	q = siz
	ans = k
	nt = n
	for i in range(1, n):
		if ans % 2 == 0:
			pp = pow(2, nt)
			xx = ans % pp
			ans = ans - xx // 2
		else:
			pp = pow(2, nt)
			xx = ans % pp
			xx = pow(2, nt) - xx - 1
			ans = ans + xx // 2
		nt = nt - 1
	print(ans)
	tt = tt - 1


T = int(input())
for t in range(T):
	s = input().split()
	n = int(s[0])
	k = int(s[1])
	if n == 0:
		print(0)
		continue
	pk = k
	f = 0
	for i in range(0, n - 1):
		if pk % 2 == 0:
			pk = pk >> 1
		else:
			f = f + (1 << n - i - 1)
			pk = pk - 1 >> 1
	print(f + pk)


import sys
twos = []
twos.append(1)
for i in range(1, 65):
	twos.append(twos[i - 1] * 2)
t = int(sys.stdin.readline())
for jj in range(0, t):
	(n, k) = map(int, sys.stdin.readline().split())
	ans = 0
	for i in range(0, n + 1):
		if k & twos[i] != 0:
			ans += twos[n - i - 1]
	print(ans)


def pos(num, N):
	s = bin(num)
	t = s[2:].zfill(N)
	r = t[::-1]
	return int(r, 2)
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	print(pos(K, N))


p2 = [1]
for i in range(2048):
	p2.append(p2[i] * 2)
t = int(input())
for _ in range(t):
	[n, k] = list(map(int, input().split()))
	k += 1
	i = n - 1
	ans = 0
	while i >= 0:
		if k > p2[i]:
			ans += p2[n - 1 - i]
			k -= p2[i]
		i -= 1
	print(ans)


T = int(input())
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	binaryK = bin(K)[2:].rjust(N, '0')
	binaryK = binaryK[::-1]
	print(int(binaryK, 2))


for _ in range(int(input())):
	(n, k) = [int(i) for i in input().strip().split()]
	k1 = '{0:0{x}b}'.format(k, x=n)
	k2 = k1[::-1]
	print(int(k2, 2))


import math as mt
test = int(input())
while test:
	test = test - 1
	(N, Q) = map(int, input().split())
	k = N - 1
	i = 0
	f = 1
	while k >= 0:
		if Q < pow(2, k):
			f = f * 2
			k = k - 1
		else:
			i = i + f
			f = f * 2
			Q = Q - pow(2, k)
			k = k - 1
	print(i)


for i in range(int(input())):
	(m, n) = map(int, input().split())
	a = bin(n)
	a = a[2:]
	a = '0' * (m - len(a)) + a
	b = 0
	for i in range(len(a)):
		b += int(a[i]) * 2 ** i
	print(b)


t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	dup = k
	bin = []
	while dup > 0:
		bin.insert(0, dup % 2)
		dup //= 2
	if len(bin) < n:
		while len(bin) < n:
			bin.insert(0, 0)
	ans = 0
	for i in range(len(bin)):
		ans = ans + bin[i] * 2 ** i
	print(ans)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	pos = k
	k = 0
	while n - k >= 2:
		t1 = pow(2, n - k)
		temp = pos // t1
		t2 = pos % t1
		if t2 % 2 == 0:
			pos = temp * t1 + t2 // 2
		else:
			pos = temp * t1 + t1 // 2 + (t2 - 1) // 2
		k += 1
	print(pos)


import sys
sys.setrecursionlimit(200000)

def calculate(k, numCards):
	if k == 0:
		return 0
	if k % 2:
		return numCards // 2 + calculate(k // 2, numCards // 2)
	else:
		return calculate(k // 2, numCards // 2)
t = int(input())
while t > 0:
	t -= 1
	(n, k) = [int(x) for x in input().split()]
	numCards = int(1 << n)
	print(int(calculate(k, numCards)))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = 0
	j = 0
	for j in range(n):
		if k % 2 != 0:
			s += 2 ** (n - 1 - j)
			k = int(k // 2)
		else:
			k = int(k // 2)
	print(s)


for t in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	l = [int(x) for x in bin(k)[2:].zfill(n)]
	ans = 0
	for i in range(len(l)):
		ans = ans + 2 ** i * l[i]
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = format(k, '0%db' % n)
	print(int(a[::-1], base=2))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	for i in range(n):
		ans += 2 ** (n - i - 1) * (k % 2)
		k >>= 1
	print(ans)


for _ in range(int(input())):
	str = list(map(int, input().split()))
	pow = 1
	for i in range(0, str[0]):
		pow = pow * 2
	ans = 0
	for _ in range(0, str[0]):
		if str[1] % 2 == 0:
			str[1] = str[1] // 2
		else:
			str[1] = (str[1] - 1) // 2
			ans = ans + pow // 2
		pow = pow // 2
	print(ans)


for q in range(int(input())):
	(n, k) = map(int, input().strip().split(' '))
	low = 0
	high = 2 ** n
	total = 0
	if k % 2 == 0:
		total = k // 2
		high = high // 2
	else:
		total = high // 2 + k // 2
		low = high // 2
	k = k // 2
	while high - low > 2:
		if k % 2 == 0:
			total -= k // 2
			high = high - (high - low) // 2
		else:
			total = low + (high - low) // 2 + k // 2
			low = low + (high - low) // 2
		k = k // 2
	print(total)


def solve():
	(N, K) = map(int, input().split())
	sz = 2
	for _ in range(N):
		x = K // sz
		y = K % sz
		if y + y < sz:
			K = y * 2 + x * sz
		else:
			K = (y - sz // 2) * 2 + 1 + x * sz
		sz <<= 1
	return K
T = int(input())
for _ in range(T):
	ans = solve()
	print(ans)


t = int(input())
for i in range(t):
	(n, p) = [int(j) for j in input().split()]
	for j in range(1, n + 1):
		q = p // (1 << j)
		r = p % (1 << j)
		if r < 1 << j - 1:
			p = (1 << j) * q + 2 * r
		else:
			p = (1 << j) * (q - 1) + 2 * r + 1
	print(p)


def f(n, k):
	if not n:
		return k
	elif k < 1 << n - 1:
		return f(n - 1, k) * 2
	else:
		return f(n - 1, k - (1 << n - 1)) * 2 + 1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(f(n, k))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = bin(k)[2:]
	s = '0' * (n - len(s)) + s
	print(int(s[::-1], 2))


for i in range(int(input())):
	(m, p) = map(int, input().split())
	n = '{0:b}'.format(p)
	t = []
	j = 0
	while j < len(n):
		t.append(int(n[j]))
		j += 1
	t.reverse()
	kk = 0
	number = 0
	while kk < len(t):
		number += 2 ** (m - kk - 1) * t[kk]
		kk += 1
	print(number)


def compute(N, K, k):
	if k == N:
		return K
	else:
		size = 2 ** (N - k)
		p = K // size
		if K % 2 == 0:
			return p * size + compute(N, K // 2, k + 1)
		else:
			return p * size + size // 2 + compute(N, K // 2, k + 1)
Q = int(input())
for q in range(Q):
	(N, K) = map(int, input().split())
	print(compute(N, K, 0))


q = int(input())
for i in range(q):
	(n, k) = map(int, input().split())
	if k % 2 == 0:
		f = k
	else:
		f = k - 1
	z = 2 ** (n - 1)
	x = z
	ans = 0
	if f >= z:
		ans += 1
	for i in range(0, n - 1):
		if f % 2 == 0:
			f //= 2
		else:
			f //= 2
			ans += x
			if f == 0:
				break
		x //= 2
	if k % 2 == 0:
		print(ans)
	else:
		print(z + ans)


cases = int(input())
from math import ceil

def func(k, left, right):
	mid = (left + right) // 2
	if (k - left) % 2 == 0:
		k = left + (k - left) // 2
		right = mid
	else:
		k = mid + (k - left) // 2
		left = mid
	return (k, left, right)
for _ in range(cases):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	(left, right) = (0, 2 ** n)
	for x in range(n):
		(k, left, right) = func(k, left, right)
	print(k)


def f(n, k):
	if k == 0:
		return 0
	if k % 2 == 0:
		return f(n - 1, k // 2)
	return f(n - 1, k // 2) + 2 ** (n - 1)
t = int(input())
while t:
	t -= 1
	[n, k] = list(map(int, input().split()))
	print(f(n, k))


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	p = 1
	pos = 0
	m = k
	p <<= n
	g = p
	q = p
	pos = k
	if k == 0 or k == p - 1:
		print(k)
	else:
		while k > 0:
			if k % 2 == 0:
				pos -= k // 2
				if pos < p - g // 2:
					p = p - g // 2
			else:
				pos += (p - 1 - pos) // 2
			k = k // 2
			g = g // 2
			if k == 3 and m > q // 2 or (k == 1 and m > q // 2):
				break
		print(pos)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	i = k
	for z in range(n):
		if z == 0:
			if k % 2 == 0:
				i = i // 2
			else:
				i = (i + (2 ** n - 1)) // 2
		else:
			b = 2 ** n // 2 ** z
			value = i // b + 1
			value1 = b * (value - 1)
			value2 = i - value1
			if value2 % 2 == 0:
				i = value1 + value2 // 2
			else:
				i = value1 + (b + value2 - 1) // 2
	print(i)


def function(N, K):
	str = format(K, 'b').zfill(N)
	str1 = str[::-1]
	a = int(str1, 2)
	return a
Q = int(input())
for i in range(0, Q):
	(N, K) = input().split(' ')
	N = int(N)
	K = int(K)
	print(function(N, K))


for i in range(int(input())):
	(a, b) = map(int, input().split())
	len = a - 1
	sum = 0
	while b:
		if b & 1:
			temp = 1 << len
			sum += temp
		len -= 1
		b >>= 1
	print(sum)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	m = n
	tot = 2 ** n
	tmp = tot
	val = 0
	tw = 2
	while m > 0:
		if k % tw != 0.0:
			val = int(val) + int(tot / 2)
			k = k - k % tw
		tot /= 2
		m -= 1
		tw *= 2
	print(int(val))


t = int(input())
for _ in range(t):
	s = input().split()
	n = int(s[0])
	k = int(s[1])
	pos = 0
	while k > 0:
		if k % 2 == 1:
			pos += 2 ** (n - 1)
		k //= 2
		n -= 1
	print(pos)


q = int(input().strip())
for _ in range(q):
	(n, k) = map(int, input().split())
	for i in range(n - 1, -1, -1):
		deck = 2 ** (n - i)
		if k % deck >= deck // 2:
			carry = 1
		else:
			carry = 0
		pos = k % (deck // 2)
		p2 = k // deck
		k = p2 * deck + 2 * pos + carry
	print(k)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	ans = 0
	count = 0
	two = 2 ** (n - 1)
	while k > 0:
		if k % 2 == 1:
			ans += two
		two >>= 1
		k >>= 1
	print(ans)


def rotate(k, i):
	m = (1 << i) - 1
	return k & ~m | (k & m) >> 1 | k << i - 1 & m
q = int(input())
for _ in range(q):
	(n, k) = map(int, input().split())
	for i in range(n, 0, -1):
		k = rotate(k, i)
	print(k)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	pos = 0
	while n >= 0:
		if k % 2 == 1:
			pos += 2 ** n
		n -= 1
		k //= 2
	print(pos // 2)


t = int(input())
while t > 0:
	(n, k) = input().split(' ')
	n = int(n)
	k = int(k)
	yo = k
	s = pow(2, n)
	s1 = pow(2, n) - 1
	for i in range(1, n):
		if yo % 2 == 0:
			new = yo % s
			nyo = new // 2
			diff = nyo - new
			yo = yo + diff
		else:
			new = yo % s
			nyo = new // 2
			nyos = nyo + s // 2
			diff = nyos - new
			yo = yo + diff
		s = s // 2
	print(yo)
	t = t - 1


for q in range(int(input())):
	temp = list(map(int, input().split()))
	n = temp[0]
	k = temp[1]
	lb = 0
	ub = 2 ** n - 1
	pos = k
	while ub - lb > 1:
		mb = (lb + ub) // 2
		if (pos - lb) % 2 == 0:
			ub = mb
			pos = lb + (pos - lb) // 2
		elif (pos - lb) % 2 == 1:
			lb = mb + 1
			pos = (pos + ub) // 2
	print(pos)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	new_post = k
	old_post = 0
	start = 0
	for i in range(0, n):
		if new_post % 2 == 0:
			org_post = start + new_post // 2
			new_post = new_post // 2
		else:
			new_post = new_post // 2
			start = start + 2 ** (n - i) // 2
			org_post = start + new_post
	print(org_post)
	t = t - 1


q = int(input())
while q:
	q = q - 1
	(n, k) = map(int, input().split())
	j = 0
	l = n
	i = 0
	x = n
	n = pow(2, n)
	while j < x:
		y = k - k % n
		if k % 2 == 0:
			k = k + y
			k = k // 2
		else:
			k = n // 2 + k % n // 2 + y
		l = l - 1
		n = pow(2, l)
		j = j + 1
	print(k)


t = input()
t = int(t)
while t > 0:
	t -= 1
	li = input()
	li2 = li.split(' ')
	i = 0
	N1 = 1 << int(li2[0]) - 1
	pre = 0
	K = int(li2[1])
	while i < int(li2[0]):
		i += 1
		if K % 2 == 0:
			K >>= 1
			K = int(K)
		else:
			K >>= 1
			K = int(K)
			pre += 1 << int(li2[0]) - i
		N1 >>= 1
		N1 = int(N1)
	print(int(pre + K))


t = int(input())
i = t
while i > 0:
	(n, k) = [int(a) for a in input().split()]
	z = 0
	while k != 0:
		x = 1
		m = 0
		while x * 2 <= k:
			x = x * 2
			m += 1
		k -= x
		z += pow(2, n - m - 1)
	print(z)
	i -= 1


test = int(input())
for i in range(test):
	(n, krr) = map(int, input().split())
	sex = 0
	j = 0
	for j in range(n):
		if krr % 2 != 0:
			sex += 2 ** (n - 1 - j)
			krr = int(krr // 2)
		else:
			krr = int(krr // 2)
	print(sex)


q = int(input())
while q > 0:
	q -= 1
	(n, k) = map(int, input().strip().split(' '))
	ans = '{0:b}'.format(k).zfill(n)[::-1]
	print(int(ans, 2))


def A(n, k):
	if k == 0:
		return 0
	if k % 2 == 0:
		return A(n - 1, k // 2)
	return A(n - 1, k // 2) + 2 ** (n - 1)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(A(n, k))


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	print(int(format(K, 'b').zfill(N)[::-1], 2))


for x in range(int(input())):
	(n, k) = map(int, input().split())
	s = str(bin(k))[2:]
	while len(s) < n:
		s = '0' + s
	s1 = s[::-1]
	print(int(s1, 2))