1008. Zero

单点时限: 2.0 sec

内存限制: 256 MB

A long time ago people found the value zero to be very useful. Just think about the romans and many more nations that didn’t know the zero. Their number representations couldn’t display the zero and that’s why they are dead now.

So you’ve got to understand the overwhelming importance of this beautiful gift of science (or nature ?) and praise the zero. That’s what you’ll do here.

Find out how many trailing zeros are at the end of n! (n factorial). That’s all you have to do, but be careful to write an efficient program, n can be really large. For example,

42! = 1405006117752879898543142606244511569936384000000000

so the answer for n=42 would be 9, since there are nine zeros at the end.

输入格式

The first line contains an integer m, the number of test cases. After that follow m lines. Every line represents one testcase, which only contains the integer number n. The value of n will be at least 1 and won’t be bigger than 2.000.000.000.

输出格式

For each testcase, print a line containing the number of trailing zeros. Do not print whitespace before or after the number.

样例

Input
4
1
23
42
2000000000
Output
0
4
9
499999997

524 人解决,801 人已尝试。

643 份提交通过,共有 1837 份提交。

2.4 EMB 奖励。

创建: 15 年前.

修改: 2 年,4 月前.

最后提交: 3 天,19 小时前.

来源: Freshman Programming Contest

题目标签