2268 - 【入门】n!末尾有多少个0

通过次数

3

提交次数

7

Time Limit : 1 秒
Memory Limit : 128 MB

计算 n! 的十进制表示最后有多少个 0

Input

第一行输入一个整数 N 表示测试数据的组数。每组测试数据占一行,都只有一个整数 M

Output

输出 M 的阶乘的十进制表示中最后 0 的个数。

比如 5!=120 则最后的 0 的个数为 1

提示 如果因式分解后,本质是查看 25 的个数。由于 2 的个数要比 5 的多。所以我们需要计算的是 n! 因式分解后 5 的个数。

数据范围 1 \le N \le 1000 \le M \le 10000000

Examples

Input

6
3
60
100
1024
23456
8735373

Output

0
14
24
253
5861
2183837

Hint

0 个数的实质就是数,里面一共有多少个 5