Phoenix has $n$ coins with weights $2^1, 2^2, \dots, 2^n$. He knows that $n$ is even.

He wants to split the coins into two piles such that each pile has exactly $\frac{n}{2}$ coins and the difference of weights between the two piles is minimized. Formally, let $a$ denote the sum of weights in the first pile, and $b$ denote the sum of weights in the second pile. Help Phoenix minimize $|a-b|$, the absolute value of $a-b$.


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \le t \le 100$) — the number of test cases.

The first line of each test case contains an integer $n$ ($2 \le n \le 30$; $n$ is even) — the number of coins that Phoenix has. 


-----Output-----

For each test case, output one integer — the minimum possible difference of weights between the two piles.


-----Example-----
Input
2
2
4

Output
2
6



-----Note-----

In the first test case, Phoenix has two coins with weights $2$ and $4$. No matter how he divides the coins, the difference will be $4-2=2$.

In the second test case, Phoenix has four coins of weight $2$, $4$, $8$, and $16$. It is optimal for Phoenix to place coins with weights $2$ and $16$ in one pile, and coins with weights $4$ and $8$ in another pile. The difference is $(2+16)-(4+8)=6$.

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
    n = int(input())
    x1 = 0
    x2 = 0
    for i in range(1, n//2):
        x1 += 2**i
    for j in range(n//2, n):
        x2 += 2**j
    x1 += 2**n
    print(abs(x1 - x2))

t = int(input())
for i in range(t):
    n = int(input())
    ans = 0
    for j in range(1, n // 2 + 1):
        ans += 2**j
    print(ans)

def main():
    n = int(input())
    sm = 0
    for i in range(1,n//2):
        sm += 2**i
    for i in range(n//2, n):
        sm -= 2**i
    sm += 2**n
    print(sm)


def __starting_point():
    t = int(input())
    for i in range(t):
        main()

__starting_point()

pot = [1] * 40
for i in range(1,40):
	pot[i] = 2 * pot[i-1]
q = int(input())
for riwe in range(q):
	n = int(input())
	wyn = pot[n]
	for i in range(n//2):
		j = n-1-i
		wyn -= pot[j]
	for i in range(1,n//2):
		wyn += pot[i]
	print(wyn)

t=int(input())
for _ in range(t):
    n=int(input())
    a=[]
    for i in range(n):
        a.append(2**(i+1))
    print(sum(a[:n//2-1])+a[-1]-sum(a[n//2-1:n-1]))

for i in range(int(input())):
	n=int(input())
	a=0
	b=0
	for j in range(int(n/2)):
		a+=2**(j+1)
		b+=2**(j+2)
	print(int(b-a))

import math
import sys

#sys.stdin = open("in.txt")

t = int(input())
for i in range(t):
    n = int(input())
    s1 = 0
    for i in range(1, n//2):
        s1 += 2**i
    s1 += 2**n
    s2 = 2**(n+1) - 2 - s1
    print(s1 - s2)

for _ in range(int(input())):
    n = int(input())
    a = 2**n
    b = 0
    for i in range(n//2):
        b += 2**(n-i-1)
    for i in range(1, n//2):
        a += 2**i
    print(abs(a-b))


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