Project Euler #16: Power digit sum

_{This problem is a programming version of Problem 16 from projecteuler.net}

and the sum of its digits is .

What is the sum of the digits of the number ?

Input Format

The first line contains an integer , i.e., number of test cases.
Next lines will contain an integer .

Constraints

Output Format

Print the values corresponding to each test case.

Sample Input

Sample Output

8
7
11

Explanation