Chef has made a list for his monthly expenses. The list has N expenses with index 1 to N. The money spent on each expense depends upon the monthly income of Chef.

Chef spends 50\% of his total income on the expense with index 1.
The money spent on the i^{th} expense (i>1) is equal to 50\% of the amount remaining, after paying for all expenses with indices less than i.

Given that Chef earns 2^{X} rupees in a month, find the amount he saves after paying for all N expenses.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two space-separated integers N and X — where N denotes the number of expenses and 2^{X} denotes the monthly income of Chef.

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

For each test case, output on a new line, the amount saved by Chef after paying for all N expenses.

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

$1 ≤ T ≤ 1000$
$1 ≤ N< X ≤ 20$

----- Sample Input 1 ------ 
4
1 2
1 3
2 3
3 4

----- Sample Output 1 ------ 
2
4
2
2
----- explanation 1 ------ 
Test case $1$: The number of expenses are $1$ and Chef's monthly income is $2^{2} = 4$.  
Chef spends $50\%$ of his monthly income, that is, $2$ on first expense and saves the remaining amount $4-2 = 2$.

Test case $2$: The number of expenses are $1$ and Chef's monthly income is $2^{3} = 8$.  
Chef spends $50\%$ of his monthly income, that is, $4$ on first expense and saves the remaining amount $8-4 = 4$.

Test case $3$: The number of expenses are $2$ and Chef's monthly income is $2^{3} = 8$.  
- Chef spends $50\%$ of his monthly income, that is, $4$ on first expense. The remaining amount is $8-4=4$.
- Chef spends $50\%$ of the remaining amount, that is, $2$ on his second expense. The remaining amount is $4-2=2$ which goes into his savings.

Test case $4$: The number of expenses are $3$ and Chef's monthly income is $2^{4} = 16$.  
- Chef spends $50\%$ of his monthly income, that is, $8$ on first expense. The remaining amount is $16-8=8$.
- Chef spends $50\%$ of the remaining amount, that is, $4$ on second expense. The remaining amount is $8-4=4$.
- Chef spends $50\%$ of the remaining amount, that is, $2$ on his third expense. The remaining amount is $4-2=2$ which goes into his savings.

Difficulty: EASY
Tags: Mathematics

Starter code:

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


import sys
for _ in range(int(sys.stdin.readline())):
	(n, x) = map(int, sys.stdin.readline().split())
	sys.stdout.write(str(2 ** (x - n)) + '\n')


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


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	amount = 2 ** x
	for i in range(n):
		per = 50 / 100 * amount
		amount -= per
	print(int(amount))


t = int(input())
for i in range(t):
	(N, X) = map(int, input().split())
	print(int(0.5 ** N * 2 ** X))


x = int(input(''))
for l in range(x):
	(x, y) = map(int, input().split())
	while x > 0:
		m = 2 ** (y - 1)
		y = y - 1
		x = x - 1
	print(m)


T = int(input())
for i in range(T):
	(N, X) = map(int, input().split())
	inc = 2 ** X
	for z in range(N):
		inc = inc - inc // 2
	print(inc)


for _ in range(int(input())):
	(a, b) = input().split()
	(a, b) = (int(a), int(b))
	x = 2 ** b
	for i in range(a):
		z = 50 / 100 * x
		x -= z
	print(int(x))


t = int(input())
for h in range(t):
	(x, y) = map(int, input().split())
	a = 2 ** y
	for i in range(x):
		a = a - a // 2
	print(a)


t = int(input())
for i in range(0, t):
	(n, x) = map(int, input().split())
	c = 2 ** x
	for j in range(n):
		d = 0.5 * c
		c = c - d
	print(int(c))


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = 2 ** x
	b = a // 2
	for i in range(n):
		l = 50 / 100 * a
		a -= l
	print(int(a))


t = int(input())
for _ in range(t):
	(num_exps, x) = map(int, input().split())
	income = 2 ** x
	for exp in range(num_exps):
		income *= 0.5
	print(int(income))


for i in range(int(input())):
	(n, x) = map(int, input().split())
	y = 2 ** x
	for j in range(n):
		y = y - y / 2
	print(int(y))


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


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	p = 2 ** x
	for i in range(n):
		per = int(1 / 2 * p)
		p -= per
	print(p)


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


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	income = 2 ** x
	for i in range(n):
		y = income // 2
		income -= y
	print(income)


def income(t):
	for _ in range(t):
		(exp, x) = map(int, input().split())
		amount = 2 ** x
		for i in range(exp):
			index = int(50 / 100 * amount)
			amount = amount - index
		print(amount)
income(int(input()))


def income(t):
	for _ in range(t):
		(exp, x) = map(int, input().split())
		first_exp = 2 ** x // 2
		final_amount = first_exp
		if exp == 1:
			print(first_exp)
		else:
			for _ in range(1, exp):
				final_amount = final_amount // 2
			print(final_amount)
income(int(input()))


for i in range(int(input())):
	(x, y) = map(int, input().split())
	a = 2
	b = 0
	j = 0
	while j < y - 1:
		a = a * 2
		j = j + 1
	j = 0
	b = a
	while j < x:
		b = b // 2
		j = j + 1
	print(b)


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


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	x = 2 ** b
	for j in range(a):
		x = x // 2
	print(x)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	e = 2 ** x
	k = 0
	for i in range(n):
		k = 0.5 * e
		e -= k
	print(int(e))


t = int(input())
for i in range(t):
	(x, n) = map(int, input().split())
	s = 2 ** n
	for i in range(x):
		s = s // 2
	print(s)


T = int(input())
for _ in range(T):
	(N, X) = map(int, input().split())
	total_earning = 2 ** X
	for i in range(N):
		ith_expense = 50 / 100 * total_earning
		total_earning = total_earning - ith_expense
	print(int(total_earning))


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


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


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	c = 2 ** b
	for i in range(a):
		minus = 50 / 100 * c
		c = c - minus
	print(int(c))


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	i = 2 ** x
	for j in range(n):
		p = 50 / 100 * i
		i -= p
	print(int(i))


testcases = int(input())
for i in range(testcases):
	(N, X) = map(int, input().split())
	amount = 2 ** X
	for i in range(N):
		per = 50 / 100 * amount
		amount -= per
	print(int(amount))


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	t = 2 ** x
	balance = 0
	while n >= 1:
		balance = balance + 2 ** (x - 1)
		n = n - 1
		x = x - 1
	print(t - balance)


def exp(x, y):
	return 2 ** (y - x)
t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	v = exp(x, y)
	print(v)


for i in range(0, int(input())):
	list1 = list(map(int, input().split()))
	print(int(2 ** list1[1] / 2 ** list1[0]))


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


for i in range(int(input())):
	(n, x) = map(int, input().split())
	s = pow(2, x)
	for i in range(1, n + 1):
		s = s // 2
	print(s)


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


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	c = 2 ** x
	for i in range(n):
		percent = 1 / 2 * c
		c -= percent
	print(int(c))


for i in range(0, int(input())):
	(a, b) = map(int, input().split())
	x = pow(2, b)
	for i in range(0, a):
		x = x // 2
	print(x)


t = int(input())
for _ in range(t):
	(n, x) = list(map(int, input().split()))
	total = 2 ** x
	for i in range(n):
		per = 50 / 100 * total
		total -= per
	print(int(total))


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = 2 ** x
	for i in range(n):
		p = 0.5 * a
		a = a - p
	print(int(a))


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


for _ in range(int(input())):
	(N, X) = map(int, input().split())
	print(2 ** (X - N))


q = int(input())
for i in range(q):
	(n, x) = map(int, input().split())
	print(2 ** x // 2 ** n)


T = int(input())
for i in range(T):
	(X, Y) = map(int, input().split())
	a = 2 ** Y
	for j in range(1, X + 1):
		b = a * 0.5
		a = a - b
	print(int(a))


n = int(input())
for i in range(n):
	(a, b) = list(map(int, input().split()))
	money = 2 ** b
	for j in range(a):
		money = money - money // 2
	print(money)


a = int(input())
for i in range(a):
	b = [int(x) for x in input().split()]
	c = 2 ** b[1]
	for i in range(b[0]):
		d = c / 2
		c = c - d
	print(int(c))


for i in range(int(input())):
	(n, x) = map(int, input().split())
	a = 2 ** x
	y = a - 50 / 100 * a
	if n == 1:
		print(int(y))
	else:
		for i in range(1, n):
			y = y - 50 / 100 * y
		print(int(y))


import math
t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	x = pow(2, x)
	while n != 0:
		x = x * 1 // 2
		n = n - 1
	print(x)


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	amount = 2 ** y
	j = 1
	while j <= x:
		amount = amount * 0.5
		j += 1
	print(int(amount))


import math
for t in range(int(input())):
	(n, x) = map(int, input().split())
	print(int(math.pow(2, x - n)))