/*
    问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;
}