#include <bits/stdc++.h>

#define int long long

int binmul (int a, int b, int M) {
	int res = 0;
	a %= M;
	while (b > 0) {
		if (b & 1) {
			res += a;
			if (res >= M) res -= M;
		}
		b >>= 1;
		a <<= 1;
		if (a >= M) a -= M;
	}
	return res;
}

int binpow (int a, int b, int M) {
	int res = 1;
	a %= M;
	while (b > 0) {
		if (b & 1) res = binmul(res, a, M);
		a = binmul(a, a, M);
		b >>= 1;
	}
	return res;
}

bool test (int a, int n, int k, int m) {
	int x = binpow(a, m, n);
	
	if (x == 1) return true;
	if (x == n - 1) return true;
	
	for (int l = 1; l < k; ++l) {
		x = binmul(x, x, n);
		if (x == n - 1) return true;
	}
	
	return false;
}

std::vector<int> build (int LIM) {
	std::vector<char> sieve (LIM + 1, true);
	sieve[0] = sieve[1] = false;
	
	std::vector<int> p {};
	p.reserve(LIM / std::log(LIM) + 10);
	
	for (int i = 2; i <= LIM; ++i) {
		if (sieve[i]) {
			p.push_back(i);
			for (int j = i * i; j <= LIM; j += i) {
				sieve[j] = false;
			}
		}
	}
	
	return p;
}

bool is_prime (int n) {
	static const int LIM = 40;
	
	static const std::vector<int> p { build(LIM) };
	
	if (std::binary_search(p.begin(), p.end(), n)) return true;
	if (n <= LIM) return false;
	
	int k = 0;
	int m = n - 1;
	
	while (m % 2 == 0) {
		++k;
		m >>= 1;
	}
	
	for (int a : p)
		if (!test(a, n, k, m))
			return false;
			
	return true;
}

void solve () {
	int n;
	std::cin >> n;
	if (is_prime(n)) std::cout << "Yes\n";
	else std::cout << "No\n";
}

signed main () {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int T = 1;
	std::cin >> T;
	while (T--) solve();

	return 0;
}