Description

$n!$ 表示 $n \times (n - 1) \times \cdots \times 3 \times 2 \times 1$ 比如 $10! = 10 \times 9 \times \cdots \times 3 \times 2 \times 1 = 3628800,$ $10!$ 的各位和是 $3 + 6 + 2 + 8 + 8 + 0 + 0 = 27$ . 输入 $n$ ，输出 $n!$ 的各位和。

Input Format

第一行输入组数 $T$ ， 接下来 $T$ 行，每行一个整数 $n$ 。 $(1 \le T \le 100$ ， $1 \le N \le 100)$

Output Format

对于每组数据，输出一个数，表示 $n!$ 的各位和

3
3
6
100

6
9
648