Factorial

Problem statement

A mathematics exhibit prints the enormous number n! on a scrolling screen. A visitor asks how many zeroes appear at the very end of that number. Printing or storing the entire factorial would be unnecessary for this question, especially for large n. You are building a compact counter that reports the trailing-zero count directly. Your task For each n, determine the number of consecutive zero digits at the end of the decimal representation of n!. The factorial is the product of the integers from 1 through n, with 0! defined as 1. Output only the count of trailing zeroes. Important details Zeroes elsewhere in the factorial do not count. Large powers of a prime may contribute more than once to the count, so checking only one factor per number is insufficient. Do not construct the complete factorial for large n. Worked example For n = 10, 10! is 3628800, which ends in two zeroes. The required output is 2.

Input format

First line: T. Next T lines: n.

Output format

Print the trailing-zero count of n! for each test case.

Constraints

1 <= T <= 10000; 0 <= n <= 1000000000.

Sample input

1
10

Sample output

2