Double Factorial

Time limit1sMemory limit128 MB

Summary

Count the trailing zeros of the product of the first n factorials, where n can reach 10^18.

Level: Medium7 of 10
Topics: Math, Binary search, Number theory
Solved: No attempts yet

Problem

For a positive integer $n$ , its factorial $n!$ is the product of all integers from $1$ to $n$ . Define the double factorial of $n$ as the product of the first $n$ factorials:

$1! \cdot 2! \cdot 3! \cdots n!$

Given $n$ , determine the number of trailing zeros in the decimal representation of this double factorial.

Input

A single line contains one integer $n$ ( $1 \le n \le 10^{18}$ ).

Output

Print a single line with the number of trailing zeros of the double factorial of $n$ .

Hint

For $n = 11$ , the double factorial equals $265790267296391946810949632000000000$ , which has $9$ trailing zeros.

Examples3

Example 1
Input
```
11
```
Expected output
```
9
```
Example 2
Input
```
1
```
Expected output
```
0
```
Example 3
Input
```
5
```
Expected output
```
1
```