Consider a playoff tournament where $2^n$ athletes compete. The athletes are numbered from $1$ to $2^n$.

The tournament is held in $n$ stages. In each stage, the athletes are split into pairs in such a way that each athlete belongs exactly to one pair. In each pair, the athletes compete against each other, and exactly one of them wins. The winner of each pair advances to the next stage, the athlete who was defeated gets eliminated from the tournament.

The pairs are formed as follows:

in the first stage, athlete $1$ competes against athlete $2$; $3$ competes against $4$; $5$ competes against $6$, and so on;

in the second stage, the winner of the match "$1$–$2$" competes against the winner of the match "$3$–$4$"; the winner of the match "$5$–$6$" competes against the winner of the match "$7$–$8$", and so on;

the next stages are held according to the same rules.

When athletes $x$ and $y$ compete, the winner is decided as follows:

if $x+y$ is odd, the athlete with the lower index wins (i. e. if $x < y$, then $x$ wins, otherwise $y$ wins);

if $x+y$ is even, the athlete with the higher index wins.

The following picture describes the way the tournament with $n = 3$ goes.

Your task is the following one: given the integer $n$, determine the index of the athlete who wins the tournament.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 30$) — the number of test cases.

Each test case consists of one line containing one integer $n$ ($1 \le n \le 30$).


-----Output-----

For each test case, print one integer — the index of the winner of the tournament.


-----Examples-----

Input
2
3
1
Output
7
1


-----Note-----

The case $n = 3$ is shown in the picture from the statement.

If $n = 1$, then there's only one match between athletes $1$ and $2$. Since $1 + 2 = 3$ is an odd number, the athlete with the lower index wins. So, the athlete $1$ is the winner.

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
import math
t = int(input())
for _ in range(t):
	n = int(input())
	print(int(math.pow(2, n) - 1))


tests = int(input())
for t in range(tests):
	n = int(input())
	players = 2 ** n
	if n == 1:
		print(1)
	else:
		print(2 ** n - 1)


testcs = int(input())
for _ in range(testcs):
	jk = int(input())
	if jk != 1:
		solu = 2 ** jk - 1
	else:
		solu = jk
	print(solu)


t = int(input())
while t > 0:
	n = int(input())
	print(2 ** n - 1)
	t -= 1


for inh in range(int(input())):
	n = int(input())
	print(2 ** n - 1)


n = int(input())
result = []
for i in range(n):
	x = int(input())
	result.append(2 ** x - 1)
print(*result, sep='\n')


import sys
linesPerTest = 1
testArguments = []
i = 0
totalLines = 1
while i <= totalLines:
	line = sys.stdin.readline().rstrip('\n')
	if i == 0:
		totalLines = linesPerTest * int(line)
	else:
		testArguments.append(line)
	i += 1
testCases = []
for j in range(0, len(testArguments), linesPerTest):
	testCases.append(testArguments[j:j + linesPerTest])

def f(testArguments):
	n = int(testArguments[0])
	if n == 1:
		return 1
	else:
		return 2 ** n - 1
for testCase in testCases:
	print(f(testCase))


t = int(input())
for x in range(t):
	a = int(input())
	print(2 ** a - 1)


import math
from bisect import bisect_left

def binarySearch(a, x):
	i = bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1

def maxSum(a):
	(max_val, curr_max, start, end, max_start, max_end) = (a[0], a[0], 0, 0, 0, 0)
	for i in range(1, len(a)):
		if curr_max + a[i] > a[i]:
			curr_max += a[i]
			end = i
		else:
			curr_max = a[i]
			start = i
			end = i
		if max_val < curr_max:
			max_val = curr_max
			max_start = start
			max_end = end
	return [max_val, max_start, max_end]

def modFact(n, p):
	if n >= p:
		return 0
	result = 1
	for i in range(1, n + 1):
		result = result * i % p
	return result

def input_int():
	return int(input())

def input_multiple():
	return map(int, input().split())
t = input_int()
while t > 0:
	n = input_int()
	print(2 ** n - 1)
	t -= 1


def main():
	n = int(input())
	return pow(2, n) - 1
for _ in range(int(input())):
	print(main())


for _ in range(int(input())):
	n = int(input())
	print(2 ** n - 1)


for h in range(int(input())):
	n = int(input())
	k = 2 ** n - 1
	print(k)


T = int(input())
for t in range(T):
	n = int(input())
	print(pow(2, n) - 1)


for _ in [0] * int(input()):
	print(2 ** int(input()) - 1)


a = int(input())
for i in range(a):
	b = int(input())
	print(2 ** b - 1)


t = int(input())
for i in range(t):
	n = int(input())
	print(2 ** n - 1)


x = int(input())
for i in range(x):
	a = int(input())
	print(2 ** a - 1)


n = int(input())
for i in range(n):
	a = int(input())
	print(2 ** a - 1)


n = int(input())
for i in range(n):
	x = int(input())
	print(2 ** x - 1)


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(n)
	else:
		a = 2 ** n - 1
		print(a)


t = int(input())
p = []
for i in range(t):
	a = int(input())
	p.append(2 ** a - 1)
print(*p, sep='\n')


T = int(input())
for z in range(0, T):
	N = int(input())
	print(2 ** N - 1)


for _ in range(int(input())):
	nyy = int(input())
	print(2 ** nyy - 1)


def winner(n):
	ans = pow(2, n)
	print(ans - 1)
for _ in range(int(input())):
	n = int(input())
	winner(n)


def solve():
	n = int(input())
	if n == 1:
		return 1
	p = 2 ** n
	return p - 1
t = int(input())
while t != 0:
	print(solve())
	t -= 1


import math
t = int(input())
for i in range(t):
	n = int(input())
	if n > 1:
		x = math.floor(math.pow(2, n) - 1)
		print(x)
	else:
		print(n)


T = int(input())
for i in range(T):
	n = int(input())
	p = 2 ** n
	print(p - 1)


testcase = int(input())
game = []
for i in range(testcase):
	temp = int(input())
	game.append(temp)
for i in game:
	win = 2 ** i - 1
	print(win)


for _ in range(int(input())):
	l = int(input())
	print(2 ** l - 1)


for i in range(int(input())):
	print(2 ** int(input()) - 1)


def result(n):
	ans = 2 ** n
	return ans - 1

def solve():
	for _ in range(int(input())):
		n = int(input())
		print(result(n))
solve()


t = int(input())
for _ in range(t):
	n = int(input())
	a = 2 ** n
	print(a - 1)


d = {1: 1, 2: 3, 3: 7, 4: 15, 5: 31, 6: 63, 7: 127, 8: 255, 9: 511, 10: 1023, 11: 2047, 12: 4095, 13: 8191, 14: 16383, 15: 32767, 16: 65535, 17: 131071, 18: 262143, 19: 524287, 20: 1048575, 21: 2097151, 22: 4194303, 23: 8388607, 24: 16777215, 25: 33554431, 26: 67108863, 27: 134217727, 28: 268435455, 29: 536870911, 30: 1073741823}
for _ in range(int(input())):
	print(d[int(input())])


def solve():
	n = int(input())
	print(2 ** n - 1)
t = int(input())
while t:
	solve()
	t = t - 1


num = int(input())
for i in range(num):
	n = int(input())
	print(2 ** n - 1)


for n in [*open(0)][1:]:
	print(2 ** int(n) - 1)


for _ in range(int(input())):
	a = int(input())
	print(2 ** a - 1)


for _ in range(int(input())):
	n = int(input())
	ans = 2
	while n > 1:
		n -= 1
		ans *= 2
	print(ans - 1)


test_cases = int(input())
for i in range(test_cases):
	n = int(input())
	print(2 ** n - 1)


for _ in range(int(input())):
	n = int(input())
	answer = pow(2, n) - 1
	print(answer)


import sys
import math

def inpu():
	return sys.stdin.readline()
lets = 'abcdefghijklmnopqrstuvwxyz'
key = {lets[i]: i for i in range(26)}
T = int(input())
for t in range(T):
	n = int(inpu())
	done = False
	a = 1
	for i in range(n):
		a *= 2
	print(a - 1)


import sys
input = sys.stdin.readline

def yes():
	print('YES')

def no():
	print('NO')
for _ in range(int(input())):
	print(2 ** int(input()) - 1)


from math import *
from sys import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from collections import Counter as ctr
from collections import deque as dq
input = stdin.readline
inp = lambda : int(input())
li = lambda : list(map(int, input().split()))
lb = lambda : list(map(int, input()))
ls = lambda : list(input())
bi = lambda n: bin(n).replace('0b', '')
yn = lambda f: print('NYOE S'[f::2])
srp = lambda s, i, c: s[:i] + c + s[i + 1:]

def solve(__=1):
	for _ in range(__):
		n = inp()
		print(2 ** n - 1)
solve(inp())


t = int(input())
for tc in range(t):
	n = int(input())
	print(2 ** n - 1)


t = int(input())
while t:
	n = int(input())
	if n == 1:
		print(1)
	else:
		print(2 ** n - 1)
	t -= 1


for iters in range(int(input())):
	n = int(input())
	print(2 ** n - 1)


def solve():
	n = int(input())
	print(2 ** n - 1)
t = int(input())
for _ in range(t):
	solve()


import math

def Solve():
	n = int(input())
	if n == 2:
		print(3)
	else:
		print(int(math.pow(2, n) - 1))
n = int(input())
while n > 0:
	Solve()
	n = n - 1


t = int(input())
for i in range(t):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(3)
	else:
		print(2 ** n - 1)


t = int(input())
for q in range(t):
	n = int(input())
	print(2 ** n - 1)


def solve():
	n = int(input())
	if n == 1:
		print(1)
		return
	print(2 ** n - 1)
tt = int(input())
for _ in range(tt):
	solve()


for tst in range(int(input())):
	n = int(input())
	print(2 ** n - 1)