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
def fact(n):
    f=1
    while(n):
        f*=n
        n-=1
    return f
def digit(r):
    s=0
    while(r):
        a=int(r%10)
        s+=a
        r=int(r/10)
    return s
for i in range(int(input())):
    a=int(input())
    q=fact(a)
    w=digit(q)
    print(w)