We know that prime numbers are positive integers that have exactly two distinct positive divisors. Similarly, we'll call a positive integer *t* Т-prime, if *t* has exactly three distinct positive divisors.

You are given an array of *n* positive integers. For each of them determine whether it is Т-prime or not.
The first line contains a single positive integer, *n* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>), showing how many numbers are in the array. The next line contains *n* space-separated integers *x*<sub class="lower-index">*i*</sub> (1 ≤ *x*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">12</sup>).

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is advised to use the cin, cout streams or the %I64d specifier.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
 
const int N = 1e6 + 10;
int prime[N], cnt;
bool st[N]; 
void init() {
	st[0] = st[1] = true;
	for(int i = 2; i <= N; i ++) {
		if(!st[i]) prime[cnt ++] = i;
		for(int j = 0; prime[j] <= N / i; j ++) {
			st[prime[j] * i] = true;
			if(i % prime[j] == 0) break;
		}
	}
}
 
void solve() {
	int n; cin >> n;
	while(n --) {
		LL a; cin >> a;
		LL p = sqrt(a);
		if((p * p == a) && !st[p]) puts("YES");
		else puts("NO");
	}
}
 
int main() {
	int t = 1;
	init();
	while(t --)
		solve();
	return 0;
}