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
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
def factsum(n):
	if n==1 or n==0:
		return 1
	s=0
	f=1
	for i in range(2,n+1):
		f*=i
		if i==5:
			f/=10
	#print f
	while f>0:
		s+=(f%10)
		f/=10
	return s
t=input()
while t>0:
	t-=1
	n=input()
	print factsum(n)