Số chữ số 0 tận cùng

Nguồn: CSES Problem Set

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

Đề bài

Cho số nguyên dương $n$. Hãy xác định số chữ số $0$ liên tiếp ở cuối biểu diễn thập phân của $n!$.

Ví dụ:

Số này có $4$ chữ số $0$ tận cùng.

Input

Dòng duy nhất chứa một số nguyên $n$.

Output

In ra số chữ số $0$ tận cùng của $n!$.

Subtask

• Subtask 1 — 15%: $1 \le n \le 20$.
• Subtask 2 — 30%: $1 \le n \le 10^6$.
• Subtask 3 — 55%: $1 \le n \le 10^9$.

Ví dụ

Input

20

Output

4

Giải thích

Với $n=20$:

Biểu diễn thập phân của $20!$ kết thúc bằng đúng $4$ chữ số $0$ liên tiếp, do đó kết quả cần in ra là $4$.