t = int(input())
for i in range(t):
    n = int(input())
    good = True
    for j in range(2, n + 1):
        if (n + 1) % j == 0:
            good = False
    if good:
        print('YES')
    else:
        print('NO')  

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

void solve(){
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
	vector<pair<int, int>> b;
	for (int i = 0; i < n; i++){
		if (b.empty() || b.back().first != a[i]){
			b.emplace_back(a[i], 1);
		}
		else{
			b.back().second++;
		}
	}
	int m = b.size();
	for (int i = 0; i < m - 1; i++){
		if (b[i].second > 1 && b[i + 1].second > 1){
			cout << m + 2 << '\n';
			return;
		}
	}
	for (int i = 0; i < m; i++){
		if (i < m - 1 && b[i].second > 1 && (i + 2 >= m || b[i + 2].first != b[i].first)){
			cout << m + 1 << '\n';
			return;
		}
		if (i > 0 && b[i].second > 1 && (i - 2 < 0 || b[i - 2].first != b[i].first)){
			cout << m + 1 << '\n';
			return;
		}
	}
	cout << m << '\n';
}

signed main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int tests = 1;
	cin >> tests;
	while(tests--){
		solve();
	}
 
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}
 

def get_k_last(l, k):
    if k < len(l):
        return l[len(l)-k:]
    else:
        return l

t = int(input())
for _ in range(t):
    n, m, x, y = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    
    c = []
    d = []
    e = []
    i = 0
    j = 0
    while i < x and j < y:
        if a[i] == b[j]:
            c.append(a[i])
            i += 1
            j += 1
        elif a[i] < b[j]:
            d.append(a[i])
            i += 1
        else:
            e.append(b[j])
            j += 1
    d.extend(a[i:])
    e.extend(b[j:])
    
    res = sorted(get_k_last(d, n) + get_k_last(e, m) + c)
    res = get_k_last(res, n + m - 1)
    print(sum(res))

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

void solve(){
	int x, y;
	cin >> x >> y;

	int su = x + y;
	int k = 0;
	while((k + 1) * (k + 2) / 2 <= su){
		k++;
	}

	int p1x = k * (k + 1) / 2 - y;
	int p1y = y;

	int p2x = x;
	int p2y = k * (k + 1) / 2 - x;

	vector<pair<int, int>> cand;
	if ((p1x + p2x) < 0){
		cand.emplace_back((p1x + p2x) / 2, k * (k + 1) / 2 - (p1x + p2x) / 2);
		cand.emplace_back((p1x + p2x - 1) / 2, k * (k + 1) / 2 - (p1x + p2x - 1) / 2);
	}
	else{
		cand.emplace_back((p1x + p2x) / 2, k * (k + 1) / 2 - (p1x + p2x) / 2);
		cand.emplace_back((p1x + p2x + 1) / 2, k * (k + 1) / 2 - (p1x + p2x + 1) / 2);
	}

	auto best = cand[0];
	for (auto [p, q] : cand){
		if (p < 0){
			p = 0;
		}
		if (q < 0){
			q = 0;
		}
		if ((p - x) * (p - x) + (q - y) * (q - y) < 
			(best.first - x) * (best.first - x) + (best.second - y) * (best.second - y)){
				best = {p, q};
		}
	}

	string ans(k, 'Y');
	for (int i = 0; i < k; i++){
		if (best.first >= k - i){
			ans[i] = 'X';
			best.first -= (k - i);
		}
	}

	cout << ans << '\n';
}

signed main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int tests = 1;
	cin >> tests;
	while(tests--){
		solve();
	}
 
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 1000043;

vector<int> g[N];
int n;

vector<int> get_dist(int x)
{
    vector<int> d(n, -1);
    d[x] = 0;
    queue<int> q;
    q.push(x);
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        for(auto y : g[k])
            if(d[y] == -1)
            {
                d[y] = d[k] + 1;
                q.push(y);
            }   
    }
    return d;
}

void remove_edge(int x, int y)
{
    int idx = -1;
    for(int i = 0; i < g[x].size(); i++)
        if(g[x][i] == y)
            idx = i;
    g[x].erase(g[x].begin() + idx, g[x].begin() + idx + 1);    
} 

vector<int> process(int v)
{
    vector<int> d(n, -1), p(n, -1);
    queue<int> q;
    q.push(v);
    d[v] = 0;
    vector<int> visited;
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        visited.push_back(k);
        for(auto y : g[k])
            if(d[y] == -1)
            {
                d[y] = d[k] + 1;
                q.push(y);
                p[y] = k;
            }
    }
    int max_dist = *max_element(d.begin(), d.end());
    vector<bool> has_end(n, false);
    has_end[v] = true;
    for(auto x : visited)
        if(d[x] == max_dist)
        {
            int cur = x;
            while(!has_end[cur])
            {
                has_end[cur] = true;
                cur = p[cur];
            }
        }

    vector<int> res;
    for(auto x : visited)
    {
        if(!has_end[x]) continue;
        int good_children = 0;
        for(auto y : g[x])
            if(p[x] != y && has_end[y]) good_children++;
        if(good_children != 1) res.push_back(d[x]);
    }   
    sort(res.begin(), res.end());
    res.erase(unique(res.begin(), res.end()), res.end());
    return res;
}

void solve()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        g[i].clear();
    for(int i = 0; i < n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    auto dist0 = get_dist(0);
    int e1 = max_element(dist0.begin(), dist0.end()) - dist0.begin();
    auto dist1 = get_dist(e1);
    int e2 = max_element(dist1.begin(), dist1.end()) - dist1.begin();
    auto dist2 = get_dist(e2);
    int d = dist1[e2];

    int x = -1, y = -1;
    for(int i = 0; i < n; i++)
        if(dist1[i] + dist2[i] == d)
        {
            if(dist1[i] == dist2[i] - 1)
                x = i;
            else if(dist1[i] == dist2[i] + 1)
                y = i;
        }

    remove_edge(x, y);
    remove_edge(y, x);
    auto ans1 = process(x);
    auto ans2 = process(y);

    vector<bool> res(n + 1);
    for(auto x : ans1)
        for(auto y : ans2)
            res[x + y + 1] = true;
    int cnt = 0;
    for(auto x : res)
        if(x) cnt++;
    cout << cnt;
    for(int i = 0; i <= n; i++)
        if(res[i])
            cout << " " << i;
    cout << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
}

#include<bits/stdc++.h>

using namespace std;

const int N = int(5e5) + 43;
const long long INF64 = (long long)(1e18);

int n;
int cost[N];

void upd(long long& x, long long y)
{
    if(x > y) x = y;
}

bool check_bit(int x, int y)
{
    return bool((x >> y) & 1);
}

long long calc_dp(const vector<vector<int>>& c)
{
    int n = c.size();
    int m = c[0].size();
    int full = (1 << m) - 1;
    vector<vector<vector<long long>>> dp(2, vector<vector<long long>>(m, vector<long long>(1 << m, INF64)));
    dp[0][0][0] = 0;
    for(int i = 0; i < n; i++)
    {
        int i1 = i & 1;
        int i2 = i1 ^ 1;
        for(int j = 0; j < m; j++)
            for(int f = 0; f < (1 << m); f++)
                dp[i2][j][f] = INF64;
        for(int j = 0; j < m; j++)
            for(int f = 0; f < (1 << m); f++)
            {
                if(dp[i1][j][f] == INF64) continue;
                int ni = i1;
                int nj = j + 1;
                if(nj == m)
                {
                    ni = i2;
                    nj = 0;
                }
                bool can = true;
                if(i > 0 && j + 2 < m && check_bit(f, m - 1) && check_bit(f, m - 2) && check_bit(f, m - 3))
                    can = false;
                if(can)
                {
                    int nf = ((f << 1) & full) | 1;
                    upd(dp[ni][nj][nf], dp[i1][j][f]); 
                }
                int nf = (f << 1) & full;
                upd(dp[ni][nj][nf], dp[i1][j][f] + c[i][j]);
            }
    }   
    return *min_element(dp[n & 1][0].begin(), dp[n & 1][0].end());
}

long long calc_comp(int x)
{
    int d2 = 0, d3 = 0;
    int p2 = 1, p3 = 1;
    while(x * (p2 * 2) <= n)
    {
        p2 *= 2;
        d2++;
    }
    while(x * (p3 * 3) <= n)
    {
        p3 *= 3;
        d3++;
    }
    d2++;
    d3++;
    vector<int> pow2(d2, 1), pow3(d3, 1);
    for(int i = 1; i < d2; i++)
        pow2[i] = pow2[i - 1] * 2;
    for(int i = 1; i < d3; i++)
        pow3[i] = pow3[i - 1] * 3;
    vector<vector<int>> cur(d3, vector<int>(d2, 0));
    for(int i = 0; i < d2; i++)
        for(int j = 0; j < d3; j++)
            if(x * 1ll * pow2[i] * 1ll * pow3[j] <= n)
                cur[j][i] = cost[x * pow2[i] * pow3[j]];
    return calc_dp(cur);
}   

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> cost[i];
    long long ans = 0;
    for(int i = 1; i <= n; i++)
        if(i % 2 != 0 && i % 3 != 0)
            ans += calc_comp(i);
    cout << ans << endl; 
}

int main()
{
    ios_base::sync_with_stdio(0);
    int t = 1;
    for(int i = 0; i < t; i++)
        solve();    
}