Các chữ số 0 tận cùng (Trailing Zeros)

Nguồn: CSES

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

Đề bài

Cho số nguyên dương $n$. Hãy tính số chữ số $0$ liên tiếp ở cuối biểu diễn thập phân của giai thừa $n!=1\cdot2\cdots n$. Giá trị $n!$ có thể rất lớn; chỉ cần in số chữ số 0 tận cùng.

Input

Một dòng chứa số nguyên dương $n$.

Output

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

Subtask

• Subtask 1 (20%): $1\le n\le100$.
• Subtask 2 (30%): $1\le n\le10^5$.
• Subtask 3 (50%): $1\le n\le10^9$.

Ví dụ

Ví dụ 1

Input

20

Output

4

Giải thích

$20!$ chứa các bội của 5 là 5,10,15,20; mỗi số đóng góp đúng một thừa số 5, nên có 4 chữ số 0 tận cùng.

Ví dụ 2

Input

25

Output

6

Giải thích

Các bội của 5 có 5 số: 5,10,15,20,25; riêng 25 có thêm một thừa số 5. Vì vậy đáp án $5+1=6$.