/*
    問n<=10^18是否能被一個數的平方整除
    將n分解為：p1p2pk  其中pi為素數，且pi<=pi+1（這里可以等于）
    若n能被一個數的平方整除，它肯定能被一個素因子的平方p^2整除，我們找到最小的這個p即可  ~~~
    1.如果p不是最后的素因子，在p之后的素數pi>=p，這時就有n>=p^3了，
       即p<=n^(1/3)，所以枚舉n^(1/3)內的素數看是否p^2|n即可，而n^(1/3)<=10^6
    2.如果p是最后的素因子，所以n的形式就是p1p2p'p^2，而p'<=p，所以P'^3<=n，p'<=n^(1/3)
       所以可以先將n的這些素因子p1,p2,,p'給去掉，p'<=n^(1/3)，所以用n^(1/3)內的素數去除即可
       最后只剩下n'=p^2，通過判斷一個數是否為完全平方數即可

    算法就是預處理10^6內的素數，用這些素數去除n，發現有p^2能整除的return即可
    否則判斷剩下的這個n'是否為完全平方數，我是用二分判斷的，加了double處理long long 溢出
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<iostream>
#include<cassert>

using namespace std;

bool isp[1000010];
int pr[300000], pn;

void init()
{
    for (int p = 2; p <= 1000000; p++) {
        if (!isp[p]) {
            pr[pn++] = p;
            for (long long j = (long long)p*p; j <= 1000000; j+= p) {
                isp[j] = 1;
            }
        }
    }
}

// n = p1p2pk

bool chk(long long n)
{
    for (int i = 0; i < pn && pr[i] <= n; i++) {
        if (n % pr[i] == 0) {
            n /= pr[i];
            if (n%pr[i] == 0) return 0;
        }
    }
    if (n == 1) {
        return 1;
    }
    long long left = 1, right = n;
    while (left <= right) {
        long long mid = (left + right) / 2;
        if ((double)mid*mid > n) right = mid - 1;//double !!
        else left = mid+1;
    }
    return right*right != n;
}


int main()
{
    //freopen("in.txt", "r", stdin);
    init();
    int T, t = 1;
    for (scanf("%d", &T); T--; ) {
        printf("Case %d: ", t++);
        long long n;
        scanf("%I64d", &n);
        puts(chk(n) ? "Yes" : "No");
    }
    return 0;
}