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.

见题面

见题面