Factorials and Trailing Zeroes

1000ms    65536K
660    208
Beginner

Description

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example, 5! = 5 * 4 * 3 * 2 * 1 = 120. The value of 0! is 1, according to the convention for an empty product.

Now your job is to find the number of trailing zeroes in the expansion of n!

For example, 1000! = 1 * 2 * 3 * ... * 1000 has 249 trailing zeroes.

Input

Multiple test cases. Each row contain a non-negative integer N (N<1000000000)

Output

For each test case, print out the number of  trailing zeroes.

Sample Input

1
5
1000

Sample Output

0
1
249

Source

Editor

keefo on 2013-12-30 07:46:16


North University of China

OnlineJudge

NUC

NOJ

OJ

ACM/ICPC