Số lượng chữ số 0

Trong một buổi phỏng vấn đặc biệt, FullHouse Dev có cơ hội gặp gỡ nhà toán học nổi tiếng Euler. Ông đã đưa ra một bài toán thú vị về việc đếm số lượng chữ số 0 ở cuối của một giai thừa.

Bài toán

Cho một số nguyên \(N\). Nhiệm vụ của bạn là tìm ra số lượng chữ số 0 ở cuối của \(N!\).

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(N\).

OUTPUT FORMAT:

• Với mỗi test case, in ra một số nguyên trên một dòng - số lượng chữ số 0 ở cuối của \(N!\).

Ràng buộc:

• \(T \leq 1000\)
• \(0 \leq N \leq 10^{11}\)

Ví dụ

INPUT

3
9
11
20

OUTPUT

1
2
4

Giải thích

• Với \(N = 9\), ta có \(9! = 362880\), kết thúc bằng 1 chữ số 0.
• Với \(N = 11\), ta có \(11! = 39916800\), kết thúc bằng 2 chữ số 0.
• Với \(N = 20\), ta có \(20!\) kết thúc bằng 4 chữ số 0.