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

Difficulty: interview

Starter code:

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)
  #print comp
  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

#!/usr/bin/env python

T = int(input())
for t in range(T):
 N = int(input())
 print(sum(map(int, str(2**N))))
 '''
    X = 2**N
    print '2^%d=%d' % (N, X)
    X = map(int, str(X))
    print '%s=%d' % ('+'.join(map(str, X)), sum(X))
    '''



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)