fact(n) refers to n×(n−1)×⋯×3×2×1

Example, fact(10)=9×⋯×3×2×1=3628800,
and the summation of the digits of fact(10) is 3+6+2+8+8+0+0=27.
Write your program to find the summation of the digits of fact(N).

Input Format

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

Output Format

Print the values corresponding to each test case.

Constraints

1≤T≤100
0≤N≤1000

SAMPLE INPUT
2
3
6

SAMPLE OUTPUT
6
9
from math import factorial

#Store factorial of 2000 in a variable a
def fun (x):
	a=factorial(x)
	
	#Typecast variable to string
	a=str(a)
	
	#print a
	
	#initialize a counter variable to add all numbers, to 0
	add=0
	
	#Iterate through the string a, i.e. factorial of 2000
	for i in a:
	    #Add each value after typecasting character into integer
	    add+=int(i)
	
	#Print sum of digits in factorial(2000)
	print add
	
t = input()
while t > 0 :
	t = t - 1;
	n = input ()
	fun(n)