Trailing Zeros

#include<stdio.h>
#include<iostream>

using namespace std;
#define ll long long

//EFFICIENT CODE FOR SEARCHING PRIME
#define MAX 1000000+7
bool a[MAX+10];
ll pr[MAX],pi;

void civ()
{
    ll i,j,k;
    pr[pi++]=2;
    for(i=4;i<=MAX;i+=2) a[i]=1;
    for(i=3;i<=MAX;i+=2)
    {
        if(a[i]==0)pr[pi++]=i;
        if(i<=1000)//1000 is sq.root of MAX
        if(a[i]==0)
        {
        //pr[pi++]=i;
        for(j=i*i;j<=MAX;j+=2*i) a[j]=1;
        }
    }
    //printf("%d",pi);
    //for(i=0;i<pi;i++)
    //printf("%d ",pr[i]);
}

ll divcount(ll n)
{
    ll divcnt=1;
    for(ll i=0;pr[i]*pr[i]<=n;i++)
    {
        ll cou=0;
        if(n%pr[i]==0)
        {
            while(n%pr[i]==0)
            {
                n/=pr[i];
                cou++;
            }
        }
        divcnt*=cou+1;
    }
    if(n>1)
        divcnt*=2;
    return divcnt;

}

int main()
{
    civ();
    ll n,t,cs;
    scanf("%lld",&t);
    for(cs=1;cs<=t;cs++)
    {
        scanf("%lld",&n);
        ll res=divcount(n);
        printf("Case %lld: %lld\n",cs,res-1);

    }


    return 0;
}