LOJ 1236

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

#define ll long long int

template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T lcm(T a,T b) {a=abs(a);b=abs(b); return (a/gcd(a,b))*b;}

#ifdef ERFANUL007
    #define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template < typename Arg1 >
    void __f(const char* name, Arg1&& arg1){
        cout << name << " = " << arg1 << std::endl;
    }
    template < typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names, ',');
        cout.write(names, comma - names) << " = " << arg1 <<" | ";
        __f(comma+1, args...);
    }
#else
    #define debug(...)
#endif

int pairsFormLCM(int n) {
    int res = 0;
    for(int i = 1; i <= n; i++ )
        for(int j = i; j <= n; j++ )
            if(lcm(i, j) == n){
                printf("%d * %d = %d\n", i, j, n);
                res++;
            }
    return res;
}

const ll N = 1e7;
bool isPrime[N + 2];
vector< ll > prime;

void sieve(){
    memset(isPrime, 1, sizeof(isPrime));

    for(int i = 4; i <= N; i += 2) isPrime[i] = 0;

    for(ll i = 3; i*i <= N; i += 2){
        if(!isPrime[i]) continue;
        for(ll j = i*i; j <= N; j += (i * 2)) isPrime[j] = 0;
    }
    prime.push_back(2LL);

    for(int i=3; i <= N; i+=2){
        if(isPrime[i]) prime.push_back(i);
    }
}

ll getcount(ll n){
    ll ans = 1;
    for(int i=0; i<prime.size() && prime[i] * prime[i] <= n; i++){
        if(n % prime[i] == 0){
            ll cnt = 0;
            while(n % prime[i] == 0){
                cnt++;
                n /= prime[i];
            }
            ans *= (cnt * 2 + 1);
        }
    }
    if(n > 1) ans *= 3;
    return (ans + 1)/2;
}

int main(){
    #ifdef ERFANUL007
        clock_t tStart = clock();
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    sieve();

    int t, cs = 0; scanf("%d", &t);

    while(t--){
        ll n; scanf("%lld", &n);
        printf("Case %d: %lld\n", ++cs, getcount(n));
    }

    #ifdef ERFANUL007
        fprintf(stderr, ">>> Runtime : %.9f\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
    #endif

    return 0;
}