Matthew really likes the number zero. In fact he likes it so much that he wants to know how many zeroes there are at the end of any factorial. So, your task is to find the number of trailing zeroes in a factorial of a given number.

The factorial of a number ~F~ is defined as the product of all natural numbers less than or equal to ~F~.

Input Specification

The first line contains the integer ~N ~ ~(1 \le N \le 10^5)~, the number of factorials Matthew wants you to check.

The next ~N~ lines will each contain the integer ~F ~ ~(1\le F \le 40~ ~000)~, meaning you have to find the number of trailing zeroes of its factorial.

Output Specification

For each ~F~, output the number of trailing zeros on its own line.

Sample Input 1

1
4

Sample Output 1

0

Sample Input 2

4
7
8
4
11

Sample Output 2

1
1
0
2