Hyunwoo the Professor

Hyunwoo, a master of algorithms, has just been appointed as a professor!

Full of high hopes, he walked into his first class, only to be disheartened when he saw that none of the students could solve the Traveling Salesman Problem (TSP).

Then he watched student Namgyu try to solve the TSP by brute force, and he was stunned. Solving the TSP by brute force takes $O(N!)$ time, which is an unbearably large amount of time.

But Namgyu does not really understand why $O(N!)$ is so large. So, to give at least a rough sense of how large $N!$ can get, Hyunwoo decides that, given a natural number $N$, he will report the number of trailing zeros at the right end of $N!$.

Right now Hyunwoo is too shocked to write any code. Please write the program on his behalf.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains a single integer $N$ ($1 \le N \le 1,000,000,000$).

For each test case, print on its own line the number of trailing zeros at the right end of $N!$.