Vivek was roaming around in the electronics shop, where he saw a box called as BlackBox. He was intrigued by its function, so he bought it. It's functionality states that for given integer input N - it outputs the sum of all the digits in factorial of N (N).
Now Vivek wants to extend its functionality for large numbers. So, he wants you to write a program that can check the correctness of the BlackBox .
INPUT :
The first line of the input contains a single integer T ( the number of test cases ). Next T lines of input contains an integer N .
OUTPUT :
For each test case, print the sum of all digits in the factorial of the corresponding input integer.
CONSTRAINTS :
for test 1, , factorial of , sum of digits = 1. for test 2, , factorial of , sum of digits = 2. for test 3, , factorial of , sum of digits = 6. for test 4, , factorial of , sum of digits = 6. for test 5, , factorial of , sum of digits = 3.
