The chef won a duet singing award at Techsurge & Mridang 2012. From that time he is obsessed with the number 2.

He just started calculating the powers of two. And adding the digits of the results.

But he got puzzled after a few calculations. So gave you the job to generate the solutions to 2^n and find their sum of digits.

-----Input-----
N : number of inputs N<=100

then N lines with input T<=2000

-----Output-----
The output for the corresponding input T

-----Example-----
Input:
3
5
10
4

Output:
5
7
7

Explanation:
2^5=32
3+2=5
2^10=1024
1+0+2+4=7
2^4=16
1+6=7

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
from operator import add
from functools import reduce
choices = []
for x in range(1800):
	num_str = list(map(int, str(2 ** x)))
	suma = reduce(add, num_str)
	choices.append(suma)
N = int(input())
for x in range(N):
	t = int(input())
	print(choices[t])


for _ in range(int(input())):
	i = int(input())
	a = str(2 ** i)
	sums = 0
	for d in a:
		d = int(d)
		sums += d
	print(sums)


import sys
for i in range(int(input())):
	n = input()
	try:
		n = int(n)
		t = 2 ** n
		s = 0
		while t > 0:
			s += t % 10
			t //= 10
		print(s)
	except:
		break


n = int(input().rstrip())
while n > 0:
	t = int(input().rstrip())
	r = 2 ** t
	r = list(str(r))
	s = 0
	for i in r:
		s = s + int(i)
	print(s)
	n = n - 1


from sys import stdin
lines = stdin.readlines()[1:]
for line in lines:
	str_2n = str(2 ** int(line))
	sum = 0
	for i in str_2n:
		sum += int(i)
	print(sum)


import sys

def main():
	s = sys.stdin.readline
	t = int(s())
	for t in range(t):
		n = int(s())
		comp = str(2 ** n)
		sum = 0
		for i in comp:
			sum += int(i)
		print(sum)

def __starting_point():
	main()
__starting_point()


import sys
line = sys.stdin.readline()
n = int(line)
while n:
	try:
		line = sys.stdin.readline()
		t = int(line)
	except:
		break
	x = 2 ** t
	sum = 0
	while x:
		sum += x % 10
		x /= 10
	print('\n%d' % sum)
	n -= 1


testcases = int(input())
while testcases:
	n = int(input())
	print(sum([int(digit) for digit in str(2 ** n)]))
	testcases -= 1


T = int(input())
for t in range(T):
	N = int(input())
	print(sum(map(int, str(2 ** N))))


N = int(input())
for i in range(N):
	res = str(2 ** int(input()))
	ans = 0
	for i in res:
		ans += ord(i) - ord('0')
	print(ans)