Hide

Problem T
Odd and Even Zeroes

In mathematics, the factorial of a positive integer number $n$ is written as $n!$ and is defined as follows:

\begin{equation*} n! = 1 \times 2 \times 3 \times 4 \times \cdots \times (n-1) \times n = \prod _{i=1}^ n{i} \end{equation*}

The value of $0!$ is considered as $1$. $n!$ grows very rapidly with the increase of $n$. Some values of $n!$ are:

\begin{align*} 0! & = 1 & 5! & = 120 \\ 1! & = 1 & 10! & = 3628800 \\ 2! & = 2 & 14! & = 87178291200 \\ 3! & = 6 & 18! & = 6402373705728000 \\ 4! & = 24 & 22! & = 1124000727777607680000 \\ \end{align*}

You can see that for some values of $n$, $n!$ has odd number of trailing zeroes (e.g. $5!$, $18!$) and for some values of $n$, $n!$ has even number of trailing zeroes (e.g. $0!$, $10!$, $22!$). Given the value of $n$, your job is to find how many of the values $0!,\, 1!,\, 2!,\, 3!,\, ...\, ,\, (n - 1)!,\, n!$ has even number of trailing zeroes.

Input

Input file contains at most 1000 lines of input. Each line contains an integer $n$ ($0 \leq n \leq 10^{18}$). Input is terminated by a line containing a $-1$.

Output

For each line of input produce one line of output. This line contains an integer which denotes how many of the numbers $0!,\, 1!,\, 2!,\, 3!,\, ...\, ,\, n!$ contains even number of trailing zeroes.

Sample Input 1 Sample Output 1
2
3
10
100
1000
2000
3000
10000
100000
200000
-1
3
4
6
61
525
1050
1551
5050
50250
100126

Please log in to submit a solution to this problem

Log in