#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<algorithm>

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<math.h>

#include<algorithm>

#include<iostream>

#include<vector>

#include<queue>

using namespace std;

typedef long long LL;

#define N 100000

#define ESP 1e-8

#define INF 0x3f3f3f3f

#define memset(a,b) memset(a,b,sizeof(a))

LL prime[N], k;

bool vis[N];

void Prime()

{

    memset(vis, false);

    k = ;

    for(int i=; i<N; i++)

    {

        if(vis[i] == )

        {

            prime[k ++] = i;

            for(int j=i+i; j<N; j+=i)

            {

                vis[j] = ;

            }

        }

    }

}

LL gcd(LL a, LL b)

{

    LL r;

    while(b)

    {

        r = a%b;

        a = b;

        b = r;

    }

    return a;

}

LL solve(LL n)

{

    LL ans, sum;

    ans = ;

    sum = ;

    int flag = ;

    for(int i=; prime[i]*prime[i] <= n; i++)

    {

        if(n%prime[i] == )

        {

            ans = ;

            while(n%prime[i] == )

            {

                n /= prime[i];

                ans ++;

            }

            if(flag == )

            {

                sum = ans;

                flag = ;

            }

            else if(flag == )

                sum = gcd(sum, ans);

        }

    }

    if(n>)

        sum = ;

    return sum;

}

int main()

{

    int T, t=;

    Prime();

    scanf("%d", &T);

    while(T --)

    {

        LL n;

        scanf("%lld", &n);

        int b = ;

        if(n<)

        {

            n = -n;

            b = ;

        }

        LL sum = solve(n);

        if(b ==  && sum% == )

        {

            while(sum% == )

                sum/=;

        }

        printf("Case %d: %lld\n", t++, sum);

    }

    return ;

}