Problem J
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 |
