#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

long long binMultiply(long long a,long long b,long long n){
    long long res=0;
    while(b){
        if(b&1) res=(res+a)%n;
        a=(a+a)%n;
        b=b>>1;
    }
    return res;
}
long long binExp(long long a,long long b,long long n){
    long long res=1;
    while(b){
        if(b&1) res=binMultiply(res,a,n);
        a=binMultiply(a,a,n);
        b=b>>1;
    }
    return res;
}

bool check_composite(long long a,long long d,long long n,int s){
    long long x=binExp(a,d,n);
    if(x==1||x==n-1) return false;

    for(int i=0;i<s-1;i++){
        x=binMultiply(x,x,n);

        if(x==n-1) return false;
    }
    return true;
}
bool MillerRabin(long long n,int iter=5){
    if(n<4) return n==3||n==2;

    int s=0;
    int d=n-1;
    while((d&1)==0){
        s++;
        d=d>>1;
    }

    for(int i=0;i<iter;i++){
        int a=2+rand()%(n-3);
        if(check_composite(a,d,n,s)) return false;
    }

    return true;


}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;cin>>t;
    while(t--){
        long long n;cin>>n;
        if(MillerRabin(n)) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }

    return 0;
}