/*
    http://oeis.org/A009003
*/

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 5 * 1000 * 1000 + 10;

bool answer[MAXN], composite[MAXN];
int Tn, n;

int main () {
    
    for(int i = 2; i * i < MAXN; i++)
        if (!composite[i])
            for(int j = i * i; j < MAXN; j += i)
                composite[j] = true;
    
    for(int i = 2; i < MAXN; i++)
        if (!composite[i] && i % 4 == 1)
            for(int j = i; j < MAXN; j += i)
                answer[j] = true;
    
    scanf("%d", &Tn);
    while (Tn--) {
        scanf("%d", &n);
        if (!answer[n])
            puts("NO");
        else
            puts("YES");
    }
    return 0;
}