# 1008. Zero

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


575 人解决，860 人已尝试。

701 份提交通过，共有 2002 份提交。

2.2 EMB 奖励。