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

int power(int a, int d, int n){
	int res = 1;
	a %= n;
	while(d > 0){
		if(d % 2 == 1)res = (res * a) % n;
		a = (a * a)% n;
		d /= 2;
	}
	return res;
}

bool millerRabin(int n, int a){
	if(n % a == 0 && n != a)return false;
	int d = n - 1;
	while(d % 2 == 0)d /= 2;
	int x = power(a,d,n);
	if(x == 1 || x == n - 1)return true;
	while(d != n - 1){
		x = (x * x) % n;
		d *= 2;
		if(x == 1)return false;
		if(x == n - 1)return true;
	}
	return false;
}
 
bool isprime(int n){
	if(n < 2)return false;
	if(n < 4)return true;
	if(n % 2 == 0)return false;
	int test[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for (int i = 0; i < 12; i++) {
        if (test[i] >= n) break;
        if (!millerRabin(n, test[i])) return false;
    }
    return true;
}
 
signed main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t; cin >> t;//max = 500 
    while(t--){
    	int n; cin >> n;
    	if(isprime(n)){
    		cout << "YES" << endl;
		}
		else cout << "NO" << endl;
	}
}