Bội của 10 trong n! (Trailing Zeros in a Factorial)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho số nguyên không âm $n$. Định nghĩa $n! = 1\cdot2\cdots n$ khi $n\ge1$ và $0!=1$. Hãy xác định có bao nhiêu chữ số $0$ liên tiếp ở cuối biểu diễn thập phân của $n!$. Không yêu cầu in giá trị giai thừa.

Input

Một dòng chứa số nguyên không âm $n$.

Output

In một số nguyên: số chữ số $0$ liên tiếp ở cuối $n!$.

Subtask

• Subtask 1 (20%): $0\le n\le100$.
• Subtask 2 (30%): $0\le n\le10^6$.
• Subtask 3 (50%): $0\le n\le10^{18}$.

Ví dụ

Ví dụ 1

Input

0

Output

0

Giải thích

Theo định nghĩa $0!=1$ nên chữ số cuối là 1, không có chữ số 0 tận cùng.

Ví dụ 2

Input

25

Output

6

Giải thích

Trong $25!$, có $\lfloor25/5\rfloor=5$ thừa số 5 từ các bội 5 và thêm $\lfloor25/25\rfloor=1$ thừa số 5 từ số 25. Tổng là $5+1=6$.