#include <bits/stdc++.h>
#define BUFF ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define FOR(a,b,i) for(int i=(a);i<=(b);i++)
#define REV(a,b,i) for(int i=(a);i>=(b);i--)
#define LOW(v,x) lower_bound(v.begin(),v.end(),x)
#define UP(v,x) upper_bound(v.begin(),v.end(),x)
#define SZ(x) ((int)x.size())
#define pb push_back
#define fi first
#define se second
#define INP(a) freopen(a,"r",stdin);
#define OUT(a) freopen(a,"w",stdout);
 
template<typename T>bool maximize(T& x,const T& y){return (x<y)?x=y,1:0;}
template<typename T>bool minimize(T& x,const T& y){return (x>y)?x=y,1:0;}
 
using namespace std;
using ll=long long;
using pa=pair<int,int>;
using str=string;
 
const int INF=1e9;
const int N=1e5+1;
const int A=1e3+1;
 
ll randInt(ll l,ll r){
	return l+rand()%(r-l+1);
}
 
ll multiply(ll a,ll k,ll n){
	ll res=0;
	while(k){
		if(k&1)res=(res+a)%n;
		a=(a+a)%n;
		k/=2;
	}
	return res;
}
 
ll binaryPower(ll a,ll k,ll n){
//	if(k==0)return 1;
	ll res=1;
	while(k){
		if(k&1)res=multiply(res,a,n);
		a=multiply(a,a,n);
		k/=2;
	}
	return res;
}
 
bool checkPrime(ll n){
	if(n==2||n==3)return 1;
	if(n<3||n%2==0||n%3==0)return 0;
 
	FOR(1,100,i){
		ll x=randInt(2,n-1);
		if(binaryPower(x,n-1,n)!=1)return 0;
	}
	return 1;
}
 
void solve(){
	int t;
	cin>>t;
	while(t--){
		ll n;
		cin>>n;
		cout<<(checkPrime(n)?"YES\n":"NO\n");
	}
}
 
int main(){
	srand(time(nullptr));
	// INP("fermat.inp")
    BUFF
    solve();
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgQlVGRiBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTtjaW4udGllKG51bGxwdHIpO2NvdXQudGllKG51bGxwdHIpOwojZGVmaW5lIEZPUihhLGIsaSkgZm9yKGludCBpPShhKTtpPD0oYik7aSsrKQojZGVmaW5lIFJFVihhLGIsaSkgZm9yKGludCBpPShhKTtpPj0oYik7aS0tKQojZGVmaW5lIExPVyh2LHgpIGxvd2VyX2JvdW5kKHYuYmVnaW4oKSx2LmVuZCgpLHgpCiNkZWZpbmUgVVAodix4KSB1cHBlcl9ib3VuZCh2LmJlZ2luKCksdi5lbmQoKSx4KQojZGVmaW5lIFNaKHgpICgoaW50KXguc2l6ZSgpKQojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Ugc2Vjb25kCiNkZWZpbmUgSU5QKGEpIGZyZW9wZW4oYSwiciIsc3RkaW4pOwojZGVmaW5lIE9VVChhKSBmcmVvcGVuKGEsInciLHN0ZG91dCk7Cgp0ZW1wbGF0ZTx0eXBlbmFtZSBUPmJvb2wgbWF4aW1pemUoVCYgeCxjb25zdCBUJiB5KXtyZXR1cm4gKHg8eSk/eD15LDE6MDt9CnRlbXBsYXRlPHR5cGVuYW1lIFQ+Ym9vbCBtaW5pbWl6ZShUJiB4LGNvbnN0IFQmIHkpe3JldHVybiAoeD55KT94PXksMTowO30KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVzaW5nIGxsPWxvbmcgbG9uZzsKdXNpbmcgcGE9cGFpcjxpbnQsaW50PjsKdXNpbmcgc3RyPXN0cmluZzsKCmNvbnN0IGludCBJTkY9MWU5Owpjb25zdCBpbnQgTj0xZTUrMTsKY29uc3QgaW50IEE9MWUzKzE7CgpsbCByYW5kSW50KGxsIGwsbGwgcil7CglyZXR1cm4gbCtyYW5kKCklKHItbCsxKTsKfQoKbGwgbXVsdGlwbHkobGwgYSxsbCBrLGxsIG4pewoJbGwgcmVzPTA7Cgl3aGlsZShrKXsKCQlpZihrJjEpcmVzPShyZXMrYSklbjsKCQlhPShhK2EpJW47CgkJay89MjsKCX0KCXJldHVybiByZXM7Cn0KCmxsIGJpbmFyeVBvd2VyKGxsIGEsbGwgayxsbCBuKXsKLy8JaWYoaz09MClyZXR1cm4gMTsKCWxsIHJlcz0xOwoJd2hpbGUoayl7CgkJaWYoayYxKXJlcz1tdWx0aXBseShyZXMsYSxuKTsKCQlhPW11bHRpcGx5KGEsYSxuKTsKCQlrLz0yOwoJfQoJcmV0dXJuIHJlczsKfQoKYm9vbCBjaGVja1ByaW1lKGxsIG4pewoJaWYobj09Mnx8bj09MylyZXR1cm4gMTsKCWlmKG48M3x8biUyPT0wfHxuJTM9PTApcmV0dXJuIDA7CgkKCUZPUigxLDEwMCxpKXsKCQlsbCB4PXJhbmRJbnQoMixuLTEpOwoJCWlmKGJpbmFyeVBvd2VyKHgsbi0xLG4pIT0xKXJldHVybiAwOwoJfQoJcmV0dXJuIDE7Cn0KCnZvaWQgc29sdmUoKXsKCWludCB0OwoJY2luPj50OwoJd2hpbGUodC0tKXsKCQlsbCBuOwoJCWNpbj4+bjsKCQljb3V0PDwoY2hlY2tQcmltZShuKT8iWUVTXG4iOiJOT1xuIik7Cgl9Cn0KCmludCBtYWluKCl7CglzcmFuZCh0aW1lKG51bGxwdHIpKTsKCS8vIElOUCgiZmVybWF0LmlucCIpCiAgICBCVUZGCiAgICBzb2x2ZSgpOwogICAgcmV0dXJuIDA7Cn0K

MTAKMTAwMDAwMDAwNwoxMDAwMDA1Mjc3CjEwMDAwMDIyNzcKNDEwNDEKNTYxCjIKOTAKMTAKMTEzCjQxCg==

10
1000000007
1000005277
1000002277
41041
561
2
90
10
113
41