Project Euler #20: Factorial digit sum

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

For example, ,
and the sum of the digits in the number is .

Find the sum of the digits in 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

2
3
6

Sample Output

6
9

Explanation