12551255 SUSTech Online Judge
Problem 1255 --[Bonus] Suffix Zero

1255: [Bonus] Suffix Zero

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 1028  Solved: 245
[Submit][Status][Web Board]

Description

Neko thinks math is interesting but he has got stuck at a math problem, so he asks you for help.

Find the number of consecutive zeros at the end of \(n!\) (in decimal representation).

Input

The first line contains a single integer \(T(1{\leq}T{\leq}10^6)\) —— the number of test case.

The \(2^{nd}\) line to the \((n+1)^{th}\) line, each line contains a single integer \(n(0{\leq}n{\leq}10^{18})\).

Output

Print the number of consecutive zeros at the end of \(n!\).

Sample Input

3
5
3
10

Sample Output

1
0
2

HINT


For the third case, 10! = 3628800, which have 2 consecutive zeros at the end.

Source

[Submit][Status]