Trailing Zeroes in Factorial

Given an integer n, compute the number of trailing zeroes in n! (the factorial of n). The number of trailing zeroes is determined by the number of times 10 is a factor in n!, which in turn depends on the number of 5s in the prime factorization (since 2s are plentiful).

You can calculate the number of trailing zeroes by the formula:

$$ \text{trailingZeroes}(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 $$

The summation stops when \( \frac{n}{5^k} \) becomes 0.

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 10⁹) provided via standard input (stdin).

outputFormat

Output a single integer — the number of trailing zeroes in n! — to standard output (stdout).

3

0