阶乘的小尾巴

题目描述

读入一个整数 $n$ ，输出 $n!$ 去掉末尾的 $0$ 后的最低 $10$ 位。如果不足 $10$ 位，在前面补足 $0$。

例如 $5!=120$ ，那么去掉末尾的 $0$ 之后，数值为 $12$，所以应该输出 $0000000012$。

请大家注意使用 64 位整数。

ps：在c语言的较新标准中，可以包含头文件 stdint.h ，然后使用数据类型 int64_t 定义64位整型。输出的时候格式控制符由 %d 改为 %lld。

输出10位不足补0的控制符为 %010lld 。

输入

第一个数为数据组数 $T$, $T\leq 10$。

接下来 $T$ 行，每行一个整数 $n$ 。 $0\leq n\leq 20000$。

输出

对于每组数据，输出一行，含义见题目描述。

输入样例

2
5
10

输出样例

0000000012
0000036288

Hint

由数论知识我们知道，在模某个数 $p$ 的意义下，是不能直接做除法的。而应该乘上除数在模 $p$ 意义下的逆元。但是本题中 $10$ 在模 $10^{10}$ 的意义下没有逆元，所以我们应该用其他算法。

我们考虑枚举 $1$ 到 $n$ 的每个数，将其乘到答案上的这个过程。我们可以先去掉它里面的 $2$ 和 $5$ 这两种因子，并分别记录一下个数。这样我们在做乘法的时候，中间过程的数末尾不会出现 $0$，我们也就不用像之前那样除以 $10$ 了，可以在中途对 $10^{10}$ 取模。最后再把剩余的 $2$ 乘到答案上即可。

本题模数和除数比较特殊，用一些其他的方法也可以卡过。