Your task is to calculate the number of trailing zeroes in the factorial n!

for example, 20! = 2432902008176640000

Input

The only input line has an integer n.

Output

Print the number of trailing zeros in n!

Constraints

• 1 <= n <= 10^9

Example

Input:

20

Output:

4

To solve this problem, we just need to count the number of 5's and number of 2s in the prime factorization of the number n.

We can see that the ending digit of the given number is 0 which is obtained only by multiplying the given number 5 with 2.

Hence, for the number of factors given number n, we can add them up and that will be our answer

Let's code the solution up.

#include<bits/stdc++.h>
using namespace std;

int getFactors(int n){
    int cnt = 0;
   while(n % 5 == 0)
    {
        n /= 5;
        cnt++;
    }
    return cnt;
}
int primeFactrization(int n)
{
    int ret = 0;
    for(int i = 5; i <= n; i += 5)
    {
        ret += getFactors(i);
    }
    return ret;
}

int main(){
    int n;
    cin >> n;
    cout << primeFactorization(n);
}

That's all we have to do in this problem, I shall see you soon in the next blog.