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 \( \le 1000 \) - 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 :

\(1 \le T \le 10^3\)

\(0 \le N \le 1000\)