#include<iostream>
#include<cmath>
#define int long long
#define maxn 210
#define maxm 1000010
using namespace std;
namespace IO{
    int read(){
        int x=0,f=1;char ch=getchar();
        while(ch<'0'||ch>'9'){
            if(ch=='-')f=-f;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+ch-'0';
            ch=getchar(); 
        }return x*f;
    }
    void print(int x){
        if(x<0){
            x=-x;
            putchar('-');
        }
        if(x>9)print(x/10);
        putchar(x%10+'0');
    }
}using namespace IO;
int q,n,a,b[maxm];
bool vis[maxm];
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a;
        b=b>>1;a=a*a;
    }return ans;
}
signed main(){
    q=read();
    for(int i=2;i<maxm;i++)vis[i]=1;
    for(int i=2;i*i<maxm+10;i++){
        if(!vis[i])continue;
        for(int j=i*2;j<maxm;j+=i)vis[j]=0;
    }
    for(int i=1;i<maxm;i++)if(vis[i])b[++a]=i;
    for(int i=1;i<=q;i++){
        n=read();
        int m;
        for(int j=1;j<maxm;j++)if(b[j]>n){m=j-1;break;}
        for(int j=1;j<=60;j++){
            for(int p=1;p<=m;p++){
                int x=qpow(b[p],j);
                if(x<0||x>n)continue;
                for(int k=1;k<=60;k++){
                    for(int c=1;c<=m;c++){
                        int y=qpow(b[c],k);
                        if(y<0||y>n)continue;
                        if(x+y==n){
                            cout<<"Yes\n";
                            goto yu;
                        }
                    }
                }       
            } 
             
        }cout<<"No\n";
        yu:continue;
    }
    return 0;
}