eolymp
bolt
Try our new interface for solving problems
Problems

Trailing Sifar

Trailing Sifar

Time limit 10 seconds
Memory limit 64 MiB

Sifar is a malay word for zero or 0. In mathematics, trailing sifar is a sequence of 0s in the decimal representation of a number after which no other digits follow.

The number of trailing sifar in the decimal representation of N! (5N1000000) is simply the multiplicity of the prime factor 5 in N!. Given a decimal integer N, you are to find the number of trailing sifar for N!

For example, 10! = 3628800. Thus, the number of trailing sifar for 10! is 2.

Input data

Each line of input contains an integer N where 5N1000000. The input is terminated with a line containing 0.

Output data

For each test case, the output contains a line in the format Case #x: M, where x is the case number (starting from 1) and M is the number of trailing sifar for N!

Examples

Input example #1
5
10
118
211
0
Output example #1
Case #1: 1
Case #2: 2
Case #3: 27
Case #4: 51
Source ACM-ICPC Malaysia al-Khawārizmī National Programming Contest 2013 (al-Khawārizmī' 2013), 21-22 September 2013