Trailing Zeros in a Factorial

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given a nonnegative integer $n$, let $n!=1\cdot2\cdots n$ for $n\ge1$ and $0!=1$. Determine the number of consecutive trailing zero digits in the decimal representation of $n!$. You do not need to print the factorial.

Input

One line contains a nonnegative integer $n$.

Output

Print one integer: the number of trailing zero digits in $n!$.

Subtasks

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

Examples

Example 1

Input

0

Output

0

Explanation

By definition, $0!=1$, which has no trailing zero.

Example 2

Input

25

Output

6

Explanation

Multiples of five contribute five factors of five, and 25 contributes one additional factor. Thus $5+1=6$.