#include<bits/stdc++.h>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#define li inline
#define re register
#define ll __int128
#define abs(a) ((a)>0?(a):-(a))
using namespace std;
namespace Miller_Rabin
{
	const int Pcnt=12;
	const ll p[Pcnt]={2,3,5,7,11,13,17,19,61,2333,4567,24251};
	li ll pow(re ll a,re ll b,re ll p)
	{
		re ll ans=1;
		for(;b;a=a*a%p,b>>=1)if(b&1)ans=ans*a%p;
		return ans;
	}
	li bool check(re ll x,re ll p)
	{
		if(x%p==0||pow(p%x,x-1,x)^1)return true;
		re ll t,k=x-1;
		while((k^1)&1)
		{
			t=pow(p%x,k>>=1,x);
			if(t^1&&t^x-1)return true;
			if(!(t^x-1))return false;
		}return false;
	}
	inline bool MR(re ll x)
	{
		if(x<2)return false;
		for(re int i=0;i^Pcnt;++i)
		{
			if(!(x^p[i]))return true;
			if(check(x,p[i]))return false;
		}return true;
	}
}
namespace Pollard_Rho
{
#define Rand(x) (1ll*rand()*rand()%(x)+1)
	li ll gcd(const ll a,const ll b){return b?gcd(b,a%b):a;}
	li ll mul(const re ll x,const re ll y,const re ll X)
	{
		ll k=(1.0L*x*y)/(1.0L*X)-1,t=x*y-k*X;
		while(t<0)t+=X;return t;
	}
	li ll PR(const re ll x,const re ll y)
	{
		re int t=0,k=1;re ll v0=Rand(x-1),v=v0,d,s=1;
		while(true)
		{
			v=(mul(v,v,x)+y)%x,s=mul(s,abs(v-v0),x);
			if(!(v^v0)||!s)return x;
			if(++t==k){if((d=gcd(s,x))^1)return d;v0=v,k<<=1;}
		}
	}
	li void Resolve(re ll x,re ll&ans)
	{
		if(!(x^1)||x<=ans)return;
		if(Miller_Rabin::MR(x)){if(ans<x)ans=x;return;}
		re ll y=x;while((y=PR(x,Rand(x)))==x);while(!(x%y))x/=y;
		Resolve(x,ans);Resolve(y,ans);
	}
	li long long check(ll x)
	{
		re ll ans=0;Resolve(x,ans);
		return ans;
	}
}
inline bool isprime(int x){return Pollard_Rho::check(x)==x;}
inline int ksm(int d,int z){
	int res=1;
	while(z){
		if(z&1)res*=d;
		d*=d;z>>=1;
	}
	return res;
}
inline int chk(int x){
	int i=2,rep=0;
	while(1){
		int res=pow(x,1.00/i);++i;
		if(ksm(res,i-1)==x&&isprime(res))return 1;
		if(res==rep)break;
		rep=res;
	}
	return 0;
}
inline bool liliang(int x){
	if(x&1){
		for(int i=1,j=0;i<=x&&j<=63;i*=2,++j){
			if(chk(x-i))return 1;
		}
		return 0;
	}
	else return 1;
}
signed main()
{
	srand(127721127);
	int Q;cin>>Q;
	while(Q--){
		int n;cin>>n;
		if(liliang(n))cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}