LOJ 1278

#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

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 divs = 1;
    for(int i=1; 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];
            }
            divs *= (cnt + 1);
        }
    }
    if(n > 1) divs *= 2;
    return divs-1;
}

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);

        while(n % 2 == 0){
            n/=2;
        }
        printf("Case %d: %lld\n", ++cs, getcount(n));
    }

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

    return 0;
}

// a1 = n/m - (m-1)/2