Counting Trailing Zeros in Factorial

Given an integer n, compute the number of consecutive trailing zeros in n! when expressed in base-10. Recall that the factorial n! (i.e., $$n! = 1 \times 2 \times \cdots \times n$$) represents the product of all positive integers from 1 to n. The number of trailing zeros is determined by the number of times 10 divides n!, which in turn depends on the factors of 5 (and 2) in the factorial. More formally, the number of trailing zeros can be calculated as:

$$Z(n) = \left\lfloor \frac{n}{5} \right\rfloor + \left\lfloor \frac{n}{5^2} \right\rfloor + \left\lfloor \frac{n}{5^3} \right\rfloor + \cdots $$

For example:

• For n = 3: \(3! = 6\), so there are 0 trailing zeros.
• For n = 5: \(5! = 120\), so there is 1 trailing zero.

inputFormat

The input consists of a single integer n (\(1 \leq n \leq 10^9\)).

outputFormat

Output a single integer representing the number of consecutive trailing zeros in n! starting from the ones digit.

sample

3

0