The Utopian Tree goes through 2 cycles of growth every year. Each spring, it doubles in height. Each summer, its height increases by 1 meter.

A Utopian Tree sapling with a height of 1 meter is planted at the onset of spring. How tall will the tree be after $n$ growth cycles?

For example, if the number of growth cycles is $n=5$, the calculations are as follows:

Period  Height
0          1
1          2
2          3
3          6
4          7
5          14

Function Description

Complete the utopianTree function in the editor below.   

utopianTree has the following parameter(s):

int n:  the number of growth cycles to simulate  

Returns  

int: the height of the tree after the given number of cycles  

Input Format

The first line contains an integer, $\boldsymbol{\boldsymbol{t}}$, the number of test cases. 

$\boldsymbol{\boldsymbol{t}}$ subsequent lines each contain an integer, $n$, the number of cycles for that test case.

Constraints

$1\leq t\leq10$ 

$0\leq n\leq60$

Sample Input
3
0
1
4

Sample Output
1
2
7

Explanation

There are 3 test cases.

In the first case ($n=0$), the initial height ($H=1$) of the tree remains unchanged.

In the second case ($n=1$), the tree doubles in height and is $2$ meters tall after the spring cycle.

In the third case ($n=4$), the tree doubles its height in spring ($n=1$, $H=2$), then grows a meter in summer ($n=2$, $H=3$), then doubles after the next spring ($n=3$, $H=6$), and grows another meter after summer ($n=4$, $H=7$). Thus, at the end of 4 cycles, its height is $7$ meters.

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	height = 1
	for i in range(N):
		if i % 2 == 0:
			height *= 2
		else:
			height += 1
	print(height)


def get_height(n):
	h = 1
	dbl = True
	for i in range(n):
		if dbl:
			h = h * 2
		else:
			h += 1
		dbl = not dbl
	print(h)
count = int(input())
ar = []
for line in range(count):
	ar.append(int(input()))
for n in ar:
	get_height(n)


import sys

def main():
	N = sys.stdin.readline()
	for i in range(0, int(N)):
		K = sys.stdin.readline()
		height = 1
		for j in range(0, int(K)):
			if j % 2 == 0:
				height *= 2
			else:
				height += 1
		print(height)
main()


import sys
from collections import deque
import heapq
from math import *
from itertools import *
PI = pi
INF = 1000000000

def gl():
	return input()

def gs():
	return (x for x in input().split())

def gi():
	return int(input())

def gis():
	return (int(x) for x in input().split())

def gf():
	return float(input())

def gfs():
	return (float(x) for x in input().split())

def even(x):
	return x % 2 == 0

def odd(x):
	return x % 2 == 1

def dbg(s):
	print(s, file=sys.stderr)
cases = gi()
for i in range(cases):
	k = gi()
	h = 1
	for j in range(k):
		if even(j):
			h *= 2
		else:
			h += 1
	print(h)


t = int(input())
for i in range(t):
	st = int(input())
	res = 1
	for j in range(st):
		if j % 2 == 0:
			res *= 2
		else:
			res += 1
	print(res)


def main():
	n = int(input())
	arrData = []
	for i in range(0, n):
		result = 1
		num = int(input())
		for j in range(1, num + 1):
			if j % 2 == 0:
				result += 1
			else:
				result *= 2
		print(result)
main()


[print((lambda x: (1 << (x >> 1) + 1) - 1 << (x & 1))(int(input()))) for i in range(int(input()))]


num = int(input())
for i in range(num):
	cyc = int(input())
	val = 1
	for i in range(cyc):
		if i % 2 == 0:
			val = val * 2
		else:
			val = val + 1
	print(val)


def deal(x):
	ans = 1
	for i in range(0, x):
		if i % 2 == 1:
			ans += 1
		else:
			ans *= 2
	print(ans)
n = int(input())
for i in range(0, n):
	t = int(input())
	deal(t)


T = int(input())
lookupTable = [1]
for i in range(1, 61):
	if i % 2 == 0:
		lookupTable.append(lookupTable[-1] + 1)
	else:
		lookupTable.append(lookupTable[-1] * 2)
while T > 0:
	T -= 1
	N = int(input())
	print(lookupTable[N])


numCases = int(input())
for case in range(0, numCases):
	cycles = int(input())
	treeHeight = 1
	for cycleNum in range(1, cycles + 1):
		if cycleNum % 2 == 1:
			treeHeight *= 2
		else:
			treeHeight += 1
	print(treeHeight)


def tree(x):
	height = 1
	p = 1
	while p <= x:
		if p % 2 == 0:
			height = height + 1
		else:
			height = height * 2
		p = p + 1
	return height
n = int(input())
while n > 0:
	t = int(input())
	print(tree(t))
	n = n - 1


T = int(input())
for i in range(T):
	N = int(input()) + 1
	k = int(N / 2)
	r = N % 2
	print(2 ** k + 2 ** k - 2 + r)


n = int(input())
for i in range(n):
	testcase = int(input())
	height = 1
	if testcase == 0:
		print(height)
	else:
		for j in range(1, testcase + 1):
			if j % 2 == 1:
				height = 2 * height
			else:
				height = height + 1
		print(height)


for i in range(0, int(input())):
	x = int(input())
	l = 1
	p = 0
	while p != x:
		if p % 2 == 0:
			l *= 2
		else:
			l += 1
		p += 1
	print(l)


testcase = int(input())
results = []
for i in range(0, testcase):
	num = int(input())
	result = 1
	for j in range(0, num):
		cycle = j % 2
		if 0 == cycle:
			result *= 2
		else:
			result += 1
	results.append(result)
for i in range(0, testcase):
	print(results[i])


T = int(input())
for i in range(T):
	curr = int(input())
	val = 1
	for j in range(curr):
		if j % 2 == 0:
			val *= 2
		else:
			val += 1
	print(val)


def odd(n):
	return n % 2 == 1

def even(n):
	return n % 2 == 0

def utopia(n):
	if n == 0:
		return 1
	elif odd(n):
		return 2 * utopia(n - 1)
	elif even(n):
		return 1 + utopia(n - 1)
t = int(input())
for i in range(0, t):
	n = int(input())
	print(utopia(n))


def calcUtopia(x):
	if x % 2 == 0:
		print(2 * 2 ** (x // 2) - 1)
	else:
		print(2 * 2 ** ((x + 1) // 2) - 2)
T = int(input())
while T > 0:
	calcUtopia(int(input()))
	T -= 1


lstOut = []
cases = int(input())
for case in range(cases):
	height = 1
	for i in range(0, int(input())):
		if i % 2 == 0:
			height *= 2
		else:
			height += 1
	lstOut.append(height)
for height in lstOut:
	print(height)


T = int(input())
for i in range(T):
	N = int(input())
	m = 2 ** (N // 2 + N % 2)
	n = 2 * (2 ** (N // 2) - 1) if N % 2 else 2 ** (N // 2) - 1
	print(n + m)


from sys import stdin
T = int(stdin.readline())
for i in range(T):
	N = int(stdin.readline())
	s = 1
	for j in range(N):
		if j % 2 == 0:
			s *= 2
		else:
			s += 1
	print(s)


def Solve(Amount, Height):
	for Time in range(Amount):
		if (Time + 1) % 2 == 0:
			Height += 1
		if (Time + 1) % 2 == 1:
			Height = Height * 2
	print(Height)
NumberOfCases = int(input())
for Cases in range(NumberOfCases):
	TreeHeight = 1
	CycleAmount = int(input())
	Solve(CycleAmount, TreeHeight)


T = int(input())
result = [1] * T
for index in range(T):
	monsoon = True
	iter = int(input())
	while iter != 0:
		if monsoon:
			result[index] *= 2
			monsoon = False
		else:
			result[index] += 1
			monsoon = True
		iter -= 1
	print(result[index])


h0 = 1
n = int(input())
for _ in range(n):
	t = int(input())
	p = (t + 1) // 2
	h = (h0 + 1) * 2 ** p - 1
	if t % 2:
		h = h - 1
	print(h)
pass


def uTree(N):
	if N == 0:
		return 1
	elif N % 2 == 0:
		return uTree(N - 1) + 1
	else:
		return uTree(N - 1) * 2
T = int(input())
N = []
for i in range(0, T):
	N.append(int(input()))
for n in N:
	print(str(uTree(n)))


t = int(input())
for i in range(t):
	n = int(input())
	height = 1
	i = 0
	while 1:
		if i == n:
			break
		else:
			height = height * 2
			i += 1
		if i == n:
			break
		else:
			height += 1
			i += 1
	print(height)


t = int(input())
for i in range(0, t):
	c = int(input())
	s = 0
	h = 1
	while c != 0:
		if s == 0:
			h *= 2
			s = 1
		else:
			h += 1
			s = 0
		c -= 1
	print(h)


def main():
	T = int(input())
	for i in range(T):
		N = int(input())
		height = 1
		for j in range(N):
			if j % 2 == 0:
				height *= 2
			else:
				height += 1
		print(height)
main()


t = int(input())
for g in range(t):
	n = int(input())
	h = 1
	for i in range(n):
		if i % 2 == 0:
			h *= 2
		else:
			h += 1
	print(h)


T = int(input())
for t in range(T):
	a = int(input())
	h = 1
	for i in range(1, a + 1):
		if i % 2 != 0:
			h *= 2
		else:
			h += 1
	print(h)


times = int(input())
for i in range(0, times):
	num = int(input())
	sol = 1
	for j in range(0, num):
		if j % 2 == 0:
			sol = 2 * sol
		else:
			sol = sol + 1
	print(sol)


for i in range(int(input())):
	N = int(input())
	print((2 ** (N // 2 + 1) - 1) * (N % 2 + 1))


t = int(input())
for i in range(t):
	n = int(input())
	ret = 1
	for j in range(n):
		if j % 2 == 0:
			ret *= 2
		else:
			ret += 1
	print(ret)


T = int(input())
i = 0
while i < T:
	N = int(input())
	n = 0
	H = 1
	while n < N:
		if n % 2 == 0:
			H *= 2
		else:
			H += 1
		n += 1
	print(str(H))
	i += 1


import sys

def utopianTree(cycles):
	heights = {}
	maxCycle = max(cycles)
	currentHeight = 1
	if 0 in cycles:
		heights[0] = currentHeight
	isMonsoon = False
	for i in range(1, maxCycle + 1):
		isMonsoon = not isMonsoon
		if isMonsoon:
			currentHeight = currentHeight * 2
		else:
			currentHeight = currentHeight + 1
		if i in cycles:
			heights[i] = currentHeight
	return heights
numTestCases = int(sys.stdin.readline())
cycles = list()
for i in range(0, numTestCases):
	cycles.append(int(sys.stdin.readline()))
heights = utopianTree(cycles)
for c in cycles:
	print(heights[c])


T = int(input())
while T > 0:
	N = int(input())
	(size, cycle) = (1, 1)
	while cycle <= N:
		if cycle % 2 == 1:
			size *= 2
		else:
			size += 1
		cycle += 1
	print(size)
	T -= 1


testcase = int(input())
for x in range(testcase):
	dp = [1]
	n = int(input())
	for i in range(1, n + 1):
		if i % 2 == 0:
			dp.append(dp[i - 1] + 1)
		else:
			dp.append(dp[i - 1] * 2)
	print(dp[n])


import sys
T = input()

def countCycles():
	N = input()
	H = 1
	x = 0
	while int(x) < int(N):
		H = int(H) * 2
		x = int(x) + 1
		if int(x) < int(N):
			H = int(H) + 1
			x = int(x) + 1
		else:
			break
	print(H)
for i in range(int(T)):
	countCycles()


n = int(input())
cases = []
for i in range(0, n):
	cases.append(int(input()))
for c in cases:
	h = 1
	for i in range(1, c + 1):
		if i % 2 == 0:
			h += 1
		else:
			h = 2 * h
	print(h)


def calculate_height(cycles):
	current_height = 1
	for cycle in range(1, cycles + 1):
		if cycle % 2 == 0:
			current_height += 1
		else:
			current_height *= 2
	return current_height
num_cases = int(input())
for _ in range(num_cases):
	print(calculate_height(int(input())))


def function(cycles, height=1):
	while cycles > 0:
		height *= 2
		cycles -= 1
		if cycles == 0:
			break
		height += 1
		cycles -= 1
	print(height)
T = int(input())
for i in range(T):
	function(int(input()))


tests = int(input())
for i in range(tests):
	N = int(input())
	height = 0
	cont = 1
	while cont <= N + 1:
		if cont % 2:
			height = height + 1
		else:
			height = height * 2
		cont += 1
	print(height)


import sys
sys.stdin.readline()
answers = [1]
input = [int(x) for x in sys.stdin]

def calculate(n):
	while len(answers) < n + 1:
		if len(answers) % 2 == 1:
			answers.append(answers[-1] * 2)
		else:
			answers.append(answers[-1] + 1)
	return answers[-1]
for n in input:
	if n < len(answers):
		print(answers[n])
	else:
		print(calculate(n))


for i in range(int(input())):
	h = 1
	for j in range(1, int(input()) + 1):
		if j % 2 == 0:
			h += 1
		else:
			h *= 2
	print(h)


def grow(h):
	i = 0
	while True:
		if i % 2 == 0:
			h = h * 2
		else:
			h = h + 1
		yield h
		i += 1
cases = int(input())
tests = [int(input()) for _ in range(cases)]
gen = grow(1)
values = [next(gen) for x in range(max(tests))]
values = [1] + values
for i in tests:
	print(values[i])


def grow(h, season):
	if season == True:
		h *= 2
	else:
		h += 1
	return h
n = int(input())
cycles = []
for x in range(0, n):
	cycles.append(int(input()))
season = True
h = 1
for i in range(0, n):
	for x in range(0, cycles[i]):
		h = grow(h, season)
		season = not season
	print(h)
	h = 1
	season = True


T = int(input())
for t in range(T):
	N = int(input())
	h = 1
	for i in range(N):
		if i % 2 == 0:
			h *= 2
		else:
			h += 1
	print(h)


N = int(input())
res = list()
for i in range(N):
	height = 1
	cycles = int(input())
	for cur_cycle in range(cycles):
		if cur_cycle % 2 == 0:
			height *= 2
		else:
			height += 1
	res.append(height)
for el in res:
	print(el)


n = int(input())

def calc(n):
	if n == 0:
		return 1
	h = 1
	for i in range(n):
		if i % 2 == 0:
			h *= 2
		else:
			h += 1
	return h
for i in range(n):
	k = calc(int(input()))
	print(k)


import sys

def calculateHeight(iteration):
	tally = 1
	for i in range(iteration):
		if i % 2 == 0:
			tally *= 2
		else:
			tally += 1
	return tally
cases = int(sys.stdin.readline())
for i in range(cases):
	iteration = int(sys.stdin.readline())
	print(calculateHeight(iteration))


n = int(input())
for i in range(n):
	k = int(input())
	print(2 ** ((k + 1) // 2 + 1) - (1 if k % 2 == 0 else 2))


from sys import stdin
T = int(stdin.readline())
assert T >= 1 and T <= 10
for i in range(1, T + 1):
	N = int(stdin.readline())
	j = 0
	height = 1
	while j < N:
		height *= 2
		j += 1
		if j >= N:
			break
		height += 1
		j += 1
	print(height)


t = int(input())
while t:
	n = int(input())
	i = 1
	j = 1
	while j <= n:
		if j % 2 == 1:
			i += i
		else:
			i += 1
		j += 1
	print(i)
	t -= 1


import sys
T = int(sys.stdin.readline())
Ns = []
for index in range(T):
	Ns.append(int(sys.stdin.readline()))
for n in Ns:
	height = 1
	for cycle in range(n):
		if cycle % 2 == 0:
			height *= 2
		else:
			height += 1
	print(height)


t = int(input())
for i in range(0, t):
	n = int(input())
	height = 1
	mon = True
	while n > 0:
		if mon == False:
			height += 1
			n -= 1
			mon = True
		elif mon == True:
			height *= 2
			n -= 1
			mon = False
	print(height)


def read_ints():
	return [int(x) for x in input().split()]
(T,) = read_ints()

def calc_hight1(cycles):
	if cycles == 0:
		return 1
	else:
		monsoons = (cycles + 1) // 2
		normals = cycles // 2
		result = pow(2, monsoons) + pow(2, monsoons) - 1
		return result

def calc_hight2(h, current, cycles):
	if current > cycles:
		return h
	if current % 2 == 1:
		return calc_hight2(h * 2, current + 1, cycles)
	else:
		return calc_hight2(h + 1, current + 1, cycles)
for tc in range(T):
	cycles = int(input())
	print(calc_hight2(1, 1, cycles))


def utopiantree(cycles):
	height = 1
	if cycles <= 0:
		return height
	else:
		counter = 0
		while counter != cycles:
			height *= 2
			counter += 1
			if counter != cycles:
				height += 1
				counter += 1
		return height
noTestCases = input()
noCyclesList = []
for i in range(int(noTestCases)):
	noCyclesList.append(int(input()))
for val in noCyclesList:
	print(utopiantree(val))


import sys

def main():
	T = input()
	for j in range(int(T)):
		plant = 1
		N = input()
		for i in range(1, 1 + int(N)):
			if i % 2 == 0:
				plant += 1
			else:
				plant = plant * 2
		print(plant)
main()


import sys

def grow(cycles):
	n = 0
	h = 1
	f = True
	while n < cycles:
		if f:
			h = h * 2
			f = False
		else:
			h = h + 1
			f = True
		n = n + 1
	return h
sys.stdin.readline()
for l in sys.stdin:
	n = int(l)
	print(grow(n))


t = int(input())
for _ in range(t):
	n = int(input())
	l = n // 2 + 1
	if n % 2 == 0:
		s = 2 ** l - 1
	else:
		s = 2 ** (l + 1) - 2
	print(s)


def fun():
	r = input()
	r1 = int(r)
	for i in range(r1):
		ip = input()
		ip1 = int(ip)
		c = 1
		tree = 1
		while ip1 != 0:
			if c % 2 == 1:
				tree = tree * 2
				c += 1
				ip1 -= 1
			else:
				tree += 1
				c += 1
				ip1 -= 1
		print(tree)
fun()


import fileinput
r = fileinput.input()
count = int(r.readline())
while count > 0:
	cycles = int(r.readline())
	h = 1
	while cycles > 0:
		h *= 2
		cycles -= 1
		if cycles > 0:
			h += 1
			cycles -= 1
	print(h)
	count -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	x = 1
	for _ in range(n // 2):
		x *= 2
		x += 1
	if n % 2 == 1:
		x *= 2
	print(x)


def isEven(n):
	return n % 2 == 0
(heights, height, t) = ([], 1, int(input()))
for i in range(t):
	for j in range(int(input())):
		if isEven(j) == True:
			height *= 2
		else:
			height += 1
	heights.append(height)
	height = 1
for height in heights:
	print(height)


T = int(input())
for i in range(T):
	n = int(input())
	h = 1
	for j in range(0, n - 1, 2):
		h = 2 * h + 1
	if n & 1:
		h *= 2
	print(h)


import sys
data = sys.stdin.readlines()
for i in range(1, int(data[0]) + 1):
	height = 1
	for j in range(int(data[i])):
		height += j % 2
		height *= 2 ** ((j + 1) % 2)
	print(height)


t = int(input())
while t:
	n = int(input())
	t -= 1
	ans = 2 ** ((n + 1) // 2 + 1) - 2 ** (n % 2)
	print(ans)


def height(cycles):
	if cycles == 0:
		return 1
	elif not cycles % 2:
		return height(cycles - 1) + 1
	else:
		return 2 * height(cycles - 1)
numtests = int(input())
tests = []
for i in range(numtests):
	tests.append(int(input()))
for test in tests:
	print(height(test))


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	height = 1
	for i in range(N):
		if i % 2 == 0:
			height *= 2
		else:
			height += 1
	print(height)


testCases = int(input())
cycles = []
while testCases:
	cycles.append(input())
	testCases -= 1
for cycle in cycles:
	cyc = int(cycle)
	tree = 1
	for x in range(0, cyc):
		if x % 2 == 0:
			tree *= 2
		else:
			tree += 1
	print(tree)


import sys
nCases = int(input())
for iCase in range(nCases):
	n = int(input())
	if n % 2 == 1:
		h = 2 * (2 ** ((n + 1) // 2) - 1)
	else:
		h = 2 * (2 ** ((n + 1) // 2) - 1) + 1
	print(h)


N = int(input())
for _ in range(N):
	x = int(input())
	height = 1
	for i in range(x):
		if i % 2 == 0:
			height *= 2
		elif i % 2 != 0:
			height += 1
	print(height)


T = int(input())
for t in range(0, T):
	N = int(input())
	h = 1
	for n in range(0, N):
		if n % 2 == 0:
			h *= 2
		else:
			h += 1
	print(h)


import sys

def grow(n):
	h = 1
	for i in range(0, n):
		if i % 2 != 0:
			h += 1
		else:
			h = h * 2
	return h
num = sys.stdin.readline()
for i in range(0, int(num)):
	print(grow(int(sys.stdin.readline())))


T = int(input())
test = [None] * T
for j in range(T):
	test[j] = int(input())

def find_height(N):
	height = 1
	for i in range(N):
		if i % 2 == 0:
			height = height * 2
		elif i % 2 == 1:
			height = height + 1
	return height
for k in range(T):
	print(find_height(test[k]))


T = int(input())
for case in range(T):
	N = int(input())
	height = 1
	for cycle in range(N):
		if cycle % 2 == 0:
			height *= 2
		else:
			height += 1
	print(height)


def CalcHightofTree(n):
	if 0 == n:
		return 1
	elif n % 2:
		return CalcHightofTree(n - 1) * 2
	else:
		return CalcHightofTree(n - 1) + 1
n = int(input())
cycles = list()
for i in range(n):
	cycles.append(int(input()))
for cycle in cycles:
	print(CalcHightofTree(cycle))


testcases = int(input())
results = list()
for testcase_i in range(testcases):
	value = 1
	n = int(input())
	for i in range(n):
		if i % 2 != 0:
			value += 1
		else:
			value *= 2
	results.append(value)
for r in results:
	print(r)


import sys

def growth(n):
	height = 1
	for i in range(n):
		if i % 2 == 1:
			height += 1
		else:
			height *= 2
	return height

def main():
	cases = int(sys.stdin.readline())
	for _ in range(cases):
		print(growth(int(sys.stdin.readline())))
main()


import functools
n = int(input())

@functools.lru_cache(maxsize=61)
def out(i):
	if i == 0:
		return 1
	elif i % 2 == 1:
		return 2 * out(i - 1)
	else:
		return out(i - 1) + 1
for _ in range(n):
	print(out(int(input())))


import sys

def cycle(start, season):
	if season:
		return start * 2
	else:
		return start + 1
first = True
for line in sys.stdin:
	if first:
		first = False
	else:
		height = 1
		count = int(line)
		for i in range(0, count):
			height = cycle(height, i % 2 == 0)
		print(height)


def Solve(Amount, Height):
	for Time in range(Amount):
		if (Time + 1) % 2 == 0:
			Height += 1
		if (Time + 1) % 2 == 1:
			Height = Height * 2
	print(Height)
NumberOfCases = int(input())
for Cases in range(NumberOfCases):
	TreeHeight = 1
	CycleAmount = int(input())
	Solve(CycleAmount, TreeHeight)


testcase = int(input())
for i in range(1, testcase + 1):
	height = 1
	cycles = int(input())
	scycles = int(cycles / 2)
	mcycles = cycles - scycles
	while mcycles != 0:
		height = height * 2
		mcycles = mcycles - 1
		if scycles != 0:
			height = height + 1
			scycles = scycles - 1
	print(height)


import sys

def run(c):
	h = 1
	for i in range(c):
		if i % 2 == 1:
			h += 1
		else:
			h *= 2
	return h
lines = sys.stdin.readlines()
T = int(lines[0])
for i in lines[1:]:
	print(run(int(i)))


def utopian(cycles):
	height = 1
	for _ in range(cycles):
		if _ % 2 == 0:
			height *= 2
		else:
			height += 1
	return height
T = int(input())
N = [int(input()) for _ in range(T)]
for _ in N:
	print(utopian(_))


t = int(input())
c = 0
while t > c:
	n = int(input())
	height = 1
	for i in range(1, n + 1):
		if i % 2 == 0:
			height += 1
		else:
			height = height * 2
	print(height)
	c += 1


scan = lambda : int(input())
t = scan()
for i in range(t):
	n = scan()
	print(2 ** ((n + 1) // 2 + 1) + -2 + (0 if n % 2 else 1))


def printUtopianHeight():
	try:
		testCases = int(input())
	except ValueError:
		print('Invalid number entered!')
		return
	for i in range(0, testCases):
		try:
			print(findUtopianHeight())
		except EOFError:
			print('Invalid number entered!')
			return

def findUtopianHeight():
	try:
		cycles = int(input())
		height = heightAfterNCycles(cycles)
		return height
	except ValueError:
		print('Invalid number entered!')
		return

def heightAfterNCycles(cycles):
	if cycles == 0:
		return 1
	elif cycles % 2 == 1:
		return 2 * heightAfterNCycles(cycles - 1)
	else:
		return heightAfterNCycles(cycles - 1) + 1
printUtopianHeight()


import sys

def main():
	testcases = int(sys.stdin.readline())
	for testcase in range(testcases):
		cycles = int(sys.stdin.readline())
		print(height_after_cycles(cycles + 1))

def height_after_cycles(cycles):
	height = 1
	for cycle in range(1, cycles):
		if cycle % 2 == 1:
			height += height
		else:
			height += 1
	return height
main()


import functools

def growth_iter_ternary(cycles):
	height = 1
	for i in range(cycles):
		height = height * 2 if i & 1 == 0 else height + 1
	return height

def growth_recursive(cycles):

	def helper(h, i):
		if i == cycles:
			return h
		h = h * 2 if i & 1 == 0 else h + 1
		return helper(h, i + 1)
	return helper(1, 0)

def growth_func(cycles):

	def grow(h, i):
		return h * 2 if i & 1 == 0 else h + 1
	vals = [1] + list(range(cycles))
	return functools.reduce(grow, vals)
testcases = int(input())
for n in range(testcases):
	x = growth_recursive(int(input()))
	print(x)


testcases = int(input())
numcycles = []
for i in range(testcases):
	nc = int(input())
	numcycles.append(nc)

def N(cycle_lst):
	for i in cycle_lst:
		result = 0
		for j in range(i + 1):
			if j % 2 == 0:
				result += 1
			else:
				result *= 2
		print(result)
N(numcycles)


import sys
T = int(sys.stdin.readline())
for case in range(T):
	N = int(sys.stdin.readline())
	ans = (2 ** (N // 2 + 1) - 1) * 2 ** (N % 2)
	print(ans)


import sys

class GrowMe(object):

	def __init__(self):
		self.growth = 0
		self.start()

	def std_grab(self):
		self.numbers_cycles = [line for line in sys.stdin]

	def full_cycle(self, var1):
		cycle = var1 * 2 + 1
		return cycle

	def start(self):
		self.std_grab()
		total_cycles = int(self.numbers_cycles[0])
		count = 1
		while count <= total_cycles:
			cycle_count = count
			runs = int(self.numbers_cycles[cycle_count])
			sub_runs = 0
			true_full_runs = runs / 2
			if runs % 2 == 0:
				while sub_runs <= true_full_runs:
					self.growth = self.full_cycle(self.growth)
					sub_runs = sub_runs + 1
			else:
				rev_runs = runs - 1
				while sub_runs <= true_full_runs:
					self.growth = self.full_cycle(self.growth)
					sub_runs = sub_runs + 1
				self.growth = self.growth * 2
			sys.stdout.write(str(self.growth) + '\n')
			self.growth = 0
			count = count + 1
runit = GrowMe()


import sys
import math
f = sys.stdin
size = int(f.readline())
i = 0
while i < size:
	val = int(f.readline())
	ret = 1
	if val == 0:
		print(ret)
	elif val == 1:
		ret += ret
		print(ret)
	else:
		for j in range(1, val + 1):
			if j % 2 == 0:
				ret += 1
			else:
				ret += ret
		print(ret)
	i += 1


def ht(n):
	if n == 0:
		return 1
	elif n % 2 == 1:
		return 2 * ht(n - 1)
	elif n % 2 == 0:
		return 2 * ht(n - 2) + 1
l = 1
t = int(input())
for i in range(t):
	x = int(input())
	print(ht(x))


import fileinput

def main():
	mylist = []
	for line in fileinput.input():
		mylist.append(line)
	num = int(mylist[0])
	for i in range(1, num + 1):
		print(calculate(int(mylist[i])))

def calculate(N):
	if N == 0:
		return 1
	elif N == 1:
		return 2
	elif N % 2 == 0:
		return calculate(N - 1) + 1
	else:
		return calculate(N - 1) * 2
main()


T = int(input())
for i in range(T):
	N = int(input())
	height = 1
	for i in range(N):
		if i % 2 == 0:
			height = height * 2
		else:
			height = height + 1
	print(height)