You are given two integers N and K. Find number of ordered triplets (A, B, C) that satisfy the following conditions:
0 ≤ A, B, C < 2^{N}
A, B and C are distinct
$A \oplus B \oplus C = K$

Here, $\oplus$ denotes the [bitwise XOR operation].

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

• The first line contains a single integer T — the number of test cases. Then the test cases follow.
• The first and only line of each test case contains two space-separated integers N and K — the parameters mentioned in the statement.

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

For each test case, output on a new line the number of triplets that satisfy the given conditions.

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

$1 ≤ T ≤ 5000$
$2 ≤N ≤20$
$0 ≤K < 2^{N}$

----- Sample Input 1 ------
3
2 1
3 0
9 100

----- Sample Output 1 ------
6
42
260610

----- explanation 1 ------
Test case $1$: There are $6$ triplets that satisfy the given conditions: $(0, 2, 3)$, $(0, 3, 2)$, $(2, 0, 3)$, $(2, 3, 0)$, $(3, 0, 2)$ and $(3, 2, 0)$.

Test case $2$: There are $42$ triplets that satisfy the given conditions, some of which are: $(1, 2, 3)$, $(1, 4, 5)$, $(6, 3, 5)$, $(7, 3, 4)$ and so on.

见题面

见题面