Read problem statements in [Russian] and [Mandarin Chinese].

Value of an array A of length L is defined as the sum of (A_{i} \oplus i) for all 0 ≤ i < L, where \oplus denotes [bitwise xor operation]. Note that array indices start from zero.
 
You are given an integer N and an array A consisting of 2^{N} integers where A_{i} = i for all 0 ≤ i < 2^{N}.
 
Example :
For N = 1, you have an array A of length 2^{1} = 2 and A = [0, 1].
For N = 2, you have an array A of length 2^{2} = 4 and A = [0, 1, 2, 3].

You can do at most K operations on this array. In one operation, you can choose two indices i and j (0 ≤ i, j < 2^{N}) and swap A_{i} and A_{j} (i.e. A_{i} becomes A_{j} and vice versa). 

What is the maximum value of array A you can obtain after at most K operations? 

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

- First line will contain T, number of testcases. Then the testcases follow.
- Each testcase contains a single line of input, two integers N, K.

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

For each testcase, output in a single line the maximum value of array after doing at most K operations.

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

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

----- Sample Input 1 ------ 
3
2 0
2 1
10 100
----- Sample Output 1 ------ 
0
6
204600
----- explanation 1 ------ 
- In the first test case, for $N = 2$, you have the array $A = [0, 1, 2, 3]$. No swap operation is 
allowed hence value of array $A = (0 \oplus 0) + (1 \oplus 1) + (2 \oplus 2) + (3 \oplus 3) = 0 + 0 + 0 + 0 = 0$. 
- In the second test case, initially the array $A = [0, 1, 2, 3]$. If you swap $A_{1}$ and $A_{2}$, $A$ becomes $[0, 2, 1, 3]$. Now value of array $A = (0 \oplus 0) + (2 \oplus 1) + (1 \oplus 2) + (3 \oplus 3) = 0 + 3 + 3 + 0 = 6$. There is no possible way such that value of array $A$ becomes greater than $6$ using one swap operation.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
for i in range(int(input())):
	(n, k) = map(int, input().split())
	max = 2 ** n - 1
	if k >= 2 ** (n - 1):
		k = 2 ** (n - 1)
	else:
		k = k
	any = 0 ^ max
	ans = any * (2 * k)
	print(ans)


t = int(input())
for i in range(1, t + 1):
	(N, k) = map(int, input().strip().split())
	max = 2 ** N - 1
	if k >= 2 ** (N - 1):
		k = 2 ** (N - 1)
	else:
		k = k
	any = 0 ^ max
	ans = any * (2 * k)
	print(ans)


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


for k in range(int(input())):
	(a, b) = map(int, input().split())
	print((2 ** a - 1) * min(2 ** a, 2 * b))


t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	s = 2 ** n - 1
	print(min(2 * k, 2 ** n) * s)
	t = t - 1


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	j = min(2 * k, 2 ** n) * (2 ** n - 1)
	print(j)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = 2 ** n - 1
	if k > 2 ** (n - 1):
		print(2 ** (n - 1) * a * 2)
	else:
		print(2 * k * a)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(min(2 * k, pow(2, n)) * (pow(2, n) - 1))


for t in range(int(input())):
	(n, k) = map(int, input().split())
	p = pow(2, n)
	m = min(p, 2 * k) * (p - 1)
	print(m)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	xyz = '1' * n
	x = int(xyz, 2)
	if k > 2 ** n // 2:
		k = 2 ** n // 2
	print(k * x * 2)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	maxi = int(2 ** n / 2)
	oneSwap = int((2 ** n - 1) * 2)
	ans = oneSwap * k
	if k > maxi:
		ans = oneSwap * maxi
	print(int(ans))


import math

def maxArrXor(n, k):
	return min(2 * k, pow(2, n)) * (pow(2, n) - 1)
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().strip().split(' '))
	print(maxArrXor(n, k))


T = int(input())
for _ in range(T):
	(n, k) = list(map(int, input().split()))
	L = pow(2, n)
	tot = 0
	if L // 2 <= k:
		tot = L // 2 * (L - 1) * 2
	else:
		tot = k * (L - 1) * 2
	print(tot)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	x = min(2 * k, 2 ** n) * (2 ** n - 1)
	print(x)


def gg():
	gh = 6 ^ 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ar_size = 2 ** n
	for ii in range(2):
		dd = 8 << 5
		fg = gg()
	print(min(k, ar_size // 2) * 2 * (ar_size - 1))


t = int(input())
while t:
	(n, k) = map(int, input().split())
	max_ele = 2 ** n - 1
	if k > 2 ** (n - 1):
		print(max_ele * 2 ** (n - 1) * 2)
	else:
		print(max_ele * k * 2)
	t -= 1


t = int(input())
for z in range(t):
	(n, k) = map(int, input().split())
	print(min(2 * k, 2 ** n) * (2 ** n - 1))


try:
	for i in range(int(input())):
		(n, s) = map(int, input().split())
		x = 2 ** n - 1
		val = min(s * 2, 2 ** n) * x
		print(val)
except:
	pass


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(min(2 * b, 2 ** a) * (2 ** a - 1))


import math
try:
	t = int(input())
except EOFError:
	pass
for i in range(t):
	count = 0
	ls = list(input().split())
	n = int(ls[0])
	k = int(ls[1])
	alen = 2 ** n
	swaps = min(int(alen / 2), k)
	maxsum = (alen - 1) * 2 * swaps
	print(maxsum)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	L = int(math.pow(2, n))
	res = min(2 * k, L) * (L - 1)
	print(res)


import io, os, sys, math
from io import BytesIO, IOBase
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	word = '1' * n
	x = int(word, 2)
	if k > 2 ** n // 2:
		k = 2 ** n // 2
	print(k * x * 2)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	val = 2 ** n
	if k <= val // 2:
		print(2 * k * (val - 1))
	else:
		print(val * (val - 1))


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	x = 2 ** N - 1
	print(min(2 * K, 2 ** N) * x)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	n = 2 ** a - 1
	m = 2 ** (a - 1)
	if b > m:
		print(n * m * 2)
	else:
		print(n * b * 2)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	(s, d) = (2 ** (n - 1), (2 ** n - 1) * 2)
	if k > s:
		print(s * d)
	else:
		print(k * d)


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


from io import BytesIO, IOBase
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	temp = pow(2, n)
	print(2 * (temp - 1) * min(k, temp // 2))


def maxarxor():
	for _ in range(int(input())):
		(N, K) = [int(x) for x in input().split()]
		if K > 2 ** N // 2:
			K = 2 ** N // 2
		print((2 ** N - 1) * K * 2)
maxarxor()


import math
T = int(input())
for i in range(T):
	(n, k) = map(int, input().split())
	l = 2 ** n
	num = l - 1
	k = min(k, l / 2)
	print(int(num * 2 * k))


for _ in range(int(input()) if True else 1):
	(n, k) = map(int, input().split())
	k = min(k, 2 ** (n - 1))
	print(2 * k * (2 ** n - 1))


try:
	T = int(input())
	for i in range(T):
		list1 = list(map(int, input().split()))
		N = list1[0]
		K = list1[1]
		max = min(2 * K, 2 ** N) * (2 ** N - 1)
		print(max)
except EOFError as e:
	print(e)


for i in range(int(input())):
	(N, K) = map(int, input().split())
	K = min(K, 2 ** (N - 1))
	print(2 * K * (2 ** N - 1))


for t in range(int(input())):
	NK = list(map(int, input().split(' ')))
	N = NK[0]
	K = NK[1]
	if K <= 2 ** (N - 1):
		print((2 ** N - 1) * K * 2)
	else:
		print((2 ** N - 1) * 2 ** N)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	val = pow(2, n) - 1
	k = min(2 * k, val + 1)
	print(val * k)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = 2 ** a - 1
	if c >= b * 2:
		print(b * 2 * c)
	else:
		print(c * (c + 1))


try:
	Test = int(input())
	for _ in range(Test):
		(N, K) = input().split()
		(N, K) = (int(N), int(K))
		L = pow(2, N)
		ANS = min(2 * K, L) * (L - 1)
		print(ANS)
except EOFError as e:
	print(e)


t = int(input())
while t > 0:
	(n, k) = list(map(int, input().split()))
	result = (2 ** n - 1) * 2 * min(k, 2 ** (n - 1))
	print(result)
	t -= 1


from math import *
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	ma = 2 ** n - 1
	maxi = min(2 ** n // 2, k)
	print(ma * maxi * 2)


t = int(input())
for j in range(t):
	(n, k) = map(int, input().split(' '))
	if k <= 2 ** (n - 1):
		print((2 ** n - 1) * 2 * k)
	else:
		print((2 ** n - 1) * 2 * 2 ** (n - 1))


t = int(input())
for _ in range(t):
	(n, k) = tuple(map(int, input().split()))
	ans = min(2 * k, 2 ** n) * (2 ** n - 1)
	print(ans)


for x in range(int(input())):
	(n, a) = map(int, input().split())
	if n == 0:
		print(0)
	else:
		print(min(2 * a, 2 ** n) * (2 ** n - 1))


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	numbers = pow(2, n)
	print(min(2 * k, numbers) * (numbers - 1))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr_len = 2 ** n
	ans = min(2 * k, arr_len) * (arr_len - 1)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if k == 0:
		print(0)
	else:
		temp = pow(2, n) - 1
		maxi = (temp + 1) // 2
		if k <= maxi:
			print(2 * k * temp)
		else:
			print(2 * maxi * temp)


cases = int(input())
for _ in range(cases):
	(a, b) = map(int, input().split())
	print(min(2 * b, 2 ** a) * (2 ** a - 1))


t = int(input())
for z in range(t):
	(n, k) = map(int, input().split())
	x = 2 ** n - 1
	if k > 2 ** (n - 1):
		print(x * 2 * 2 ** (n - 1))
	else:
		print(x * 2 * k)


for t in range(int(input())):
	inp = input().split()
	n = int(inp[0])
	k = int(inp[1])
	k = min(k, 2 ** (n - 1))
	val = 2 * k * (2 ** n - 1)
	print(val)


import sys
T = int(sys.stdin.readline())
for i in range(T):
	(N, K) = map(int, sys.stdin.readline().strip().split())
	mx = min(2 * K, pow(2, N)) * (pow(2, N) - 1)
	sys.stdout.write(str(mx) + '\n')


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	if k == 0:
		print(0)
	else:
		print((pow(2, n + 1) - 2) * min(2 ** (n - 1), k))


t = int(input())
while t:
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	Range = 2 ** n - 1
	val = min(k * 2, Range + 1) * Range
	print(val)
	t -= 1


import sys
import math
import heapq
from collections import defaultdict as dd
from collections import OrderedDict as od
from collections import deque
from itertools import permutations as pp
from itertools import combinations as cc
from sys import stdin
from functools import cmp_to_key
from functools import lru_cache
from bisect import bisect_left as bs_l
from bisect import bisect_right as bs_r
input = sys.stdin.readline
mod = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 5)

def helper(s):
	pass
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	xx = pow(2, n)
	if k >= xx // 2:
		print(xx * (xx - 1))
	else:
		print(2 * k * (xx - 1))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	x = pow(2, n)
	m = min(2 * k, x)
	print((x - 1) * m)


import math
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	ls = int(math.pow(2, n))
	lf = ls
	ls -= 1
	ans = int(0)
	m = int(lf / 2)
	if k <= m:
		ans = 2 * k * ls
	elif k > m:
		ans = 2 * m * ls
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = 2 ** n - 1
	b = min(2 * k, 2 ** n)
	ans = b * a
	print(ans)


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	a = pow(2, N - 1)
	if K > a:
		print((pow(2, N) - 1) * 2 * a)
	else:
		print((pow(2, N) - 1) * 2 * K)


try:
	t = int(input())
	out = [-1] * t
	for i in range(t):
		[n, k] = input().split(' ')
		n = int(n)
		k = int(k)
		out[i] = min(2 * k, 2 ** n) * (2 ** n - 1)
	for i in range(t):
		print(out[i])
except:
	pass


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = 2 ** n
	ans = min(2 * k, l) * (l - 1)
	print(ans)


import sys
input = lambda : sys.stdin.readline()
int_arr = lambda : list(map(int, input().split()))
str_arr = lambda : list(map(str, input().split()))
get_str = lambda : map(str, input().split())
get_int = lambda : map(int, input().split())
get_flo = lambda : map(float, input().split())
mod = 1000000007

def solve():
	pass
for _ in range(int(input())):
	(a, b) = get_int()
	totalshift = min(b, 2 ** a // 2)
	print(2 * totalshift * (2 ** a - 1))


import math
for _ in range(int(input())):
	(n, k) = map(int, input().strip().split())
	x = int(math.pow(2, n) - 1)
	y = x // 2 + 1
	if k >= y:
		k = y
	print(x * (k * 2))


for _ in range(int(input())):
	(n, k) = map(int, input().strip().split())
	x = 2 ** n - 1
	if k >= x // 2 + 1:
		print(x * ((x // 2 + 1) * 2))
	else:
		print(x * (k * 2))


for t in range(int(input())):
	(N, K) = map(int, input().split())
	mxn = 2 ** N
	print(min(K, mxn // 2) * (mxn - 1) * 2)


for _ in range(int(input())):
	(n, k) = [int(w) for w in input().split()]
	w = 2 ** n
	if k >= w // 2:
		print((w - 1) * w)
	else:
		print((w - 1) * (2 * k))


T = int(input())
outputs = []
for i in range(T):
	(N, K) = map(int, input().split())
	if K > 2 ** (N - 1):
		K = 2 ** (N - 1)
	outputs.append(2 * K * (2 ** N - 1))
for i in range(T):
	print(outputs[i])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(min(2 * m, 2 ** n) * (2 ** n - 1))


import math

def func1(n, k):
	z = pow(2, n)
	if k <= 0:
		return 0
	k = min(2 * k, z)
	maximum = k * (z - 1)
	return maximum
t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	print(func1(n, k))
	t -= 1