Trailing Zeros

Source: CSES

Version: Phuoc Hung OJ Extended

Problem Statement

Given a positive integer $n$, calculate the number of consecutive trailing zeros in the decimal representation of the factorial $n!=1\cdot2\cdots n$. You only need to output the number of trailing zeros, not the factorial.

Input

One line contains the positive integer $n$.

Output

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

Subtasks

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

Examples

Example 1

Input

20

Output

4

Explanation

$20!$ contains the four multiples 5,10,15,20; each contributes one factor five, so there are four trailing zeros.

Example 2

Input

25

Output

6

Explanation

There are five multiples of five and 25 contributes one more factor, giving six zeros.