Đếm số 0

Source http://ntucoder.net/Problem/Details/3330

Cho một số nguyên ~n~. Hãy đếm xem trong kết quả của số ~n!~ (n giai thừa) có bao nhiêu chữ số ~0~ liên tiếp tính từ hàng đơn vị (hay bao nhiêu số ~0~ liên tiếp bên phải).

Input

Dòng đầu tiên chứa ~T (1<=T<=100) ~ -Số trường hợp thử.

T dòng tiếp theo, chứa ~n(1 \le n \le 10^{16})~.

Output

~T~ dòng, là số lượng chữ số ~0~ liên tiếp tính từ hàng đơn vị của ~n!~.

Sample Input

3
4
8
20

Sample Output

0
1
4