Consider the following algorithm
order(arr, i) {
if length(arr) <= 1 {
return arr
}
l = []  
r = []
n = length(arr) - 1
for j in 0, 1, ..., n {
if ( (arr[j] modulo power(2,i+1))  < power(2,i) ) {
append arr[j] to l
}else{
append arr[j] to r
}
}
l = order(l, i + 1)
r = order(r, i + 1)
c = concatenate(l, r)
return c
}

Note that $concatenate(l, r)$ returns an array which is the array $l$, followed by the array $r$. Similarly $power(x,y)$ returns $x^y$.
Let $a$ be the array $a_0,a_1,a_2,a_3, \ldots,a_n$ where $a_j = j$ for each index $j$ and the last index $n = (2^p-1)$ for a fixed integer parameter $p$.  Given an integer $p$ and an index $idx$, your task is calculate the element at index $idx$ in the array returned by executing $order(a, 0)$.
For example, suppose $ p = 3$ and $idx = 3$.
- The initial array is $a = [0, 1, 2, 3, 4, 5, 6, 7]$.
- Executing $order(a, 0)$ first creates two new arrays $l == [0, 2, 4, 6]$ and $r == [1, 3, 5, 7]$.
- Next, $order(l, 1)$ and $order(r, 1)$ are executed.
- $order(l, 1)$, in turn, executes $order([0, 4], 2)$ and $order([2, 6], 2)$ which return $[0, 4]$ and $[2, 6]$, respectively. These are then concatenated, so $order(l, 1)$ returns $[0, 4, 2, 6]$.
- Similarly, $order(r, 1)$ returns $[1, 5, 3, 7]$.
- These two are concatenated as the final result, so the array returned by $order(a, 0)$ is $[0, 4, 2, 6, 1, 5, 3, 7]$.
So, if the input is $p = 3$, and $idx = 3$, the answer is $6$. If $p = 3$ and $idx = 7$, the answer should be $7$.

-----Input Format:-----
- The first line contains a single integer, $T$, which is the number of testcases. The description of each testcase follows.
- Each testcase is described by a single line with two integers: $p$ and $idx$, where $p$ is the parameter that determines the length of the array $a$ and $idx$ is the index at which you have to report the value in the output of $order(a, 0)$.

-----Output Format:-----
- You should print the answer in a new line for each testcase, which should be a single integer, the element at index $idx$ after executing $order(a, 0)$ for the array $a$ defined by the parameter $p$.

-----Constraints:-----
- $1 \leq T \leq 10$ 
- $1 \leq p \leq 50$
- $0 \leq idx \leq 2^p-1$

-----SUBTASKS:-----
- Subtask 1: 20% points : $1 \leq p \leq 20$
- Subtask 2: 80% points: Original constraints

-----Sample Input:-----
2
3 3
3 7

-----Sample Output:-----
6
7

-----Explanation:-----
Both the testcases have been explained in the problem statement.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
for _ in range(int(input())):
	(p, idx) = map(int, input().split())
	b = bin(idx)[2:]
	b = ('0' * (p - len(b)) + b)[::-1]
	print(int(b, 2))


t = int(input())
for _ in range(t):
	(p, idx) = list(map(int, input().split()))
	length = 2 ** p
	somma = 0
	mult = 1
	while length > 1:
		length = length >> 1
		if idx >= length:
			idx -= length
			somma += mult
		mult *= 2
	print(somma)


try:
	t = int(input())
	for _ in range(t):
		(p, idx) = map(int, input().split())
		print(int(bin(idx)[2:].zfill(p)[::-1], 2))
except:
	pass


t = input()
for i in range(int(t)):
	inp = input()
	(p, idx) = (int(inp.split()[0]), inp.split()[1])
	binidxlist = [i for i in bin(int(idx))[2:]]
	binidx = ''
	for j in binidxlist:
		binidx += j
	binidx = int(binidx[::-1] + '0' * (p - len(binidx)), 2)
	print(binidx)


def order(arr, i):
	if len(arr) <= 1:
		return arr
	l = arr[::2]
	r = arr[1::2]
	l = order(l, i + 1)
	r = order(r, i + 1)
	c = l + r
	return c
t = int(input())
while t > 0:
	(p, idx) = list(map(int, input().split()))
	a = []
	sizeinp = pow(2, p) - 1
	for i in range(sizeinp + 1):
		a.append(i)
	print(order(a, 0)[idx])
	t -= 1


def order(arr):
	if len(arr) <= 1:
		return arr
	l = arr[::2]
	r = arr[1::2]
	l = order(l)
	r = order(r)
	c = l + r
	return c
for _ in range(int(input())):
	(p, idx) = list(map(int, input().split()))
	seq = list(range(2 ** p))
	print(order(seq)[idx])


t = int(input())
for k in range(t):
	(p, i) = input().split()
	(p, i) = (int(p), int(i))
	arr = []
	for j in range(p):
		if i >> j & 1:
			arr.append(1)
		else:
			arr.append(0)
	arr = arr[::-1]
	ans = 0
	for j in range(p):
		if arr[j] == 1:
			ans += 2 ** j
	print(ans)


t = int(input())
for _ in range(t):
	(p, id1) = list(map(int, input().split()))
	n = pow(2, p) - 1
	l = []
	res = 0
	while p > 0:
		l.append(int(id1 % 2))
		id1 = id1 / 2
		p -= 1
	for i in l:
		res = res * 2 + i
	print(res)


t = int(input())
for _ in range(t):
	(p, idx) = list(map(int, input().split()))
	n = 2 ** p - 1
	l = []
	s = 0
	while p > 0:
		l.append(int(idx % 2))
		idx = idx / 2
		p -= 1
	for i in l:
		s = s * 2 + i
	print(s)


t = int(input())

def power(a, b):
	return a ** b

def concatenate(a, b):
	return a + b

def order(arr, i):
	if len(arr) <= 1:
		return arr
	l = []
	r = []
	n = len(arr)
	for j in range(n):
		if arr[j] % power(2, i + 1) < power(2, i):
			l.append(arr[j])
		else:
			r.append(arr[j])
	l = order(l, i + 1)
	r = order(r, i + 1)
	c = concatenate(l, r)
	return c
for _ in range(t):
	(p, idx) = list(map(int, input().split()))
	n = 2 ** p - 1
	l = []
	s = 0
	while p > 0:
		l.append(int(idx % 2))
		idx = idx / 2
		p -= 1
	for i in l:
		s = s * 2 + i
	print(s)
	t -= 1


ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda : int(input())
ip = lambda : [int(w) for w in input().split()]
for _ in range(inp()):
	(k, ind) = ip()
	ans = 0
	while k:
		ans = 2 * ans + ind % 2
		ind //= 2
		k -= 1
	print(ans)


def log_(n):
	(x, c) = (1, 0)
	while True:
		x *= 2
		if x > n:
			break
		c += 1
	return c
for _ in range(int(input())):
	(p, idx) = list(map(int, input().split()))
	ans = 0
	while idx > 0:
		d = log_(idx)
		ans += pow(2, p - d - 1)
		idx -= pow(2, d)
	print(ans)


for _ in range(int(input())):
	(p, i) = map(int, input().split())
	p = 1 << p - 1
	j = 0
	ans = 0
	while p > 0:
		if i >= p:
			ans += 1 << j
			i -= p
		p >>= 1
		j += 1
	print(ans)


def calc(i, p):
	if p == 1:
		return [0, 1][i]
	if i >= 2 ** (p - 1):
		t = calc(i - 2 ** (p - 1), p)
		return t + 1
	else:
		t = calc(i, p - 1)
		return 2 * t
for t in range(int(input())):
	[p, i] = [int(i) for i in input().split()]
	print(calc(i, p))


def find_value(index, last):
	if last < 2:
		return index
	if index > last // 2:
		new_last = last // 2
		new_index = new_last - (last - index)
		return find_value(new_index, new_last) * 2 + 1
	else:
		new_last = last // 2
		new_index = index
		return find_value(new_index, new_last) * 2

def find_value_at_index(p, idx):
	last = (1 << p) - 1
	assert idx <= last
	return find_value(idx, last)
T = int(input())
for x in range(T):
	(p, i) = [int(x) for x in input().split()]
	print(find_value_at_index(p, i))