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.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Mathematics


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


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


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split(' '))
	if b > 2 ** a - 1:
		print(0)
	else:
		ans = 4
		s = 4
		for j in range(a - 1):
			ans = ans * 4
			s = 2 * s + 2
		print(ans - s)


for _ in range(int(input())):
	n = 1 << list(map(int, input().split()))[0]
	print((n - 1) * (n - 2))


for _ in range(int(input())):
	l = list(map(int, input().split()))
	x = l[0]
	y = 2 ** x
	print((y - 1) * (y - 2))


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


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


q = [0] * 21
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = (1 << n) - 1
	print(x * (x - 1))


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


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


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


t = int(input())
for i in range(t):
	l = list(map(int, input().split()))
	n = l[0]
	m = 2 ** n
	print((m - 1) * (m - 2))


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


def main():
	T = int(input())
	for _ in range(T):
		(N, K) = map(int, input().split())
		print(pow(4, N) - 3 * ((1 << N) - 1) - 1)
main()


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


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


def data():
	(x, y) = map(int, input().split())
	max = 1 << x
	print((max - 1) * (max - 2))
a = int(input())
while a > 0:
	a = a - 1
	data()


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


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


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


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split(' '))
	count = 0
	r = 2 ** n
	res = (r - 1) * (r - 2)
	print(res)


MOD = 1000000007
t = int(input())
while t > 0:
	(N, K) = map(int, input().split())
	max = 1 << N
	print((max - 1) * (max - 2))
	t -= 1


t = int(input())
while t:
	(n, k) = map(int, input().split())
	print((pow(2, n) - 1) * (pow(2, n) - 2))
	t -= 1


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


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


def Binexp(a, n):
	ans = 1
	while n > 0:
		if n & 1:
			ans *= a
		a *= a
		n >>= 1
	return ans

def solve():
	(n, k) = map(int, input().split())
	ans = (Binexp(2, n) - 1) * (Binexp(2, n) - 2)
	return ans
for _ in range(int(input())):
	print(solve())


t = int(input())
while t:
	(n, k) = map(int, input().split())
	mod = 10 ** 9 + 7
	power = pow(2, n, mod)
	print((power - 1) * (power - 2))
	t -= 1


tc = int(input())
while tc:
	(N, K) = map(int, input().split())
	m = 1 << N
	print((m - 1) * (m - 2))
	tc -= 1


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


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


import sys
import os
import math
import collections
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	A = 2 ** N
	B = (A - 1) * (A - 2)
	print(B)


for i in range(int(input())):
	(num1, num2) = map(int, input().split(' '))
	ans = 2 ** num1
	print((ans - 1) * (ans - 2))


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


import sys
input = sys.stdin.readline
M = int(1000000000.0) + 7

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


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


import sys
f = sys.stdin
next(f)
for s in f:
	n = int(s.split()[0])
	m = 1 << n
	print((m << n) - 3 * m + 2)


t = int(input())
for k in range(t):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	print(4 ** n - (3 * 2 ** n - 2))


for t in range(int(input())):
	(n, k) = list((int(i) for i in input().split()))
	l = len(bin(k))
	l -= 2
	if l > n:
		print(0)
	else:
		print(4 ** n - 3 * 2 ** n + 2)


for _ in range(int(input())):
	(n, y) = map(int, input().split())
	res = 1
	k = n
	for i in range(k):
		res *= 4
	res -= ((1 << n) - 1) * 3
	print(res - 1)


import sys
input = sys.stdin.readline

def xor(n, k):
	cnt = 0
	nn = n
	n = 2 ** n
	print((2 ** nn - 2) * (n - 1))

def dense(n, s):
	cnt = 0
	left = 0
	right = n - 1
	while left <= right:
		if s[left] == ')':
			cnt += 1
			left += 1
			continue
		if s[right] == '(':
			cnt += 1
			right -= 1
			continue
		if s[left] == '(':
			left += 1
		if s[right] == ')':
			right -= 1
	print(cnt)
for t in range(int(input())):
	(n, k) = map(int, input().split())
	xor(n, k)


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


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	ans = 1
	k = n
	while k:
		ans *= 4
		k -= 1
	ans -= ((1 << n) - 1) * 3
	print(ans - 1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	result = 1
	k = n
	for i in range(k):
		result *= 4
	result -= ((1 << n) - 1) * 3
	print(result - 1)


t = int(input())
while t:
	(n, k) = map(int, input().split())
	k = n
	res = 1
	while k:
		res *= 4
		k -= 1
	res -= ((1 << n) - 1) * 3 + 1
	print(res)
	t -= 1


t = int(input())
for _ in range(t):
	(n, x) = input().split(' ')
	n = int(n)
	ans = (2 ** n - 1) * (2 ** n - 2)
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	res = 1
	k = n
	while k > 0:
		res = res * 4
		k -= 1
	a = 1 << n
	res = res - (a - 1) * 3
	print(res - 1)


t = int(input())
for i in range(0, t):
	(n, x) = map(int, input().split())
	k = n
	res = 1
	while k != 0:
		res = res * 4
		k = k - 1
	res = res - (2 ** n - 1) * 3
	print(res - 1)


for _ in range(int(input())):
	(a, b) = [int(i) for i in input().split()]
	res = pow(2, a) - 1
	print(int(res * (res - 1)))


t1 = int(input())
for i in range(t1):
	(n1, k1) = map(int, input().split())
	ans = 1
	a1 = n1
	while a1 != 0:
		ans *= 4
		a1 -= 1
	ans -= ((1 << n1) - 1) * 3
	print(ans - 1)


import math
t = int(input())
while t > 0:
	t -= 1
	ip = input().split()
	(n, k) = [int(x) for x in ip]
	print(pow(4, n) - (pow(2, n) - 1) * 3 - 1)


for tc in range(int(input())):
	(n, k) = map(int, input().split(' '))
	res = 1
	k = n
	while k:
		res = res * 4
		k -= 1
	res -= ((1 << n) - 1) * 3
	print(res - 1)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().strip().split(' '))
	ans = 1
	temp = n
	while temp:
		ans *= 4
		temp -= 1
	ans -= ((1 << n) - 1) * 3
	print(ans - 1)


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


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