lightoj1028

CODE

#include <iostream>

using namespace std;
int cnt,ncase;
bool vis[1000005];
int p[500005];
void get()
{
        for(int i=2;i<=(1000000);i++)       if(!vis[i])
        {
                p[cnt++]=i;
                for(int j=i;j<=(1000000);j+=i)
                {
                        vis[j]=1;
                }
        }

}
int main()
{
        int t;
        cin >> t;
        get();
        while(t--)
        {
                long long n;
                cin >> n;
                long long ans=1;
                int i;
                for(i=0;i<cnt&&1ll*p[i]*p[i]<=n;i++)
                {
                        int num=0;
                        while(n%p[i]==0)
                        {
                                n/=p[i];
                                num++;
                        }
                        ans *= num+1;
                }
                if(n>1)ans*=2;
                cout<<"Case "<<++ncase<<": "<<ans-1<<endl;
        }
        return 0;
}