#include <iostream>
#include <algorithm>
using namespace std;
using u64 = unsigned long long;
using f80 = long double;

u64 uz = time(NULL);
u64 xorshift64() {
  uz ^= uz << 13;
  uz ^= uz >> 7;
  uz ^= uz << 17;
  return uz;
}

u64 mypow(u64 a, u64 b) {
  u64 res = 1ULL;
  while(b) {
    if(b & 1) { res *= a; }
    a *= a;
    b >>= 1;
  }
  return res;
}

u64 mod_mul(u64 a, u64 b, u64 m) {
  u64 res = 0;
  a %= m;
  while(b) {
    if(b & 1) { (res += a) %= m; }
    (a <<= 1) %= m;
    b >>= 1;
  }
  return res;
}

u64 mod_pow(u64 x, u64 k, u64 m) {
  if(k == 0) { return 1; }
  if(!(k & 1)) { return mod_pow(mod_mul(x, x, m), k>>1, m); }
  return mod_mul(x, mod_pow(x, k-1, m), m);
}

bool is_probable_prime(u64 n) {
  constexpr int k = 30;
  if(n < 2) { return false; }
  for(u64&& p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}) {
    if(n < p * p)  { return true; }
    if(n % p == 0) { return false; }
  }
  u64 s = 0,
      d = n-1;
  while(!(d & 1)) { ++s, d>>=1; }
  for(int loop=0; loop<k; ++loop) {
    u64 a = xorshift64() % (n-3) + 2,
        x = mod_pow(a, d, n);
    if(x == 1 || x == n-1) { continue; }
    bool flag = false;
    for(u64 loop2=1; loop2<s; ++loop2) {
      x = mod_mul(x, x, n);
      if(x == n-1) { flag = true; break; }
    }
    if(!flag) { return false; }
  }
  return true;
}

u64 g(u64 pa, int a) {
  u64 lo = 1, hi = powl(pa, f80(1)/a) + 1;
  while(hi - lo > 1) {
    u64 md = (lo + hi) / 2;
    if(mypow(md, a) <= pa) { lo = md; }
    else { hi = md; }
  }
  return lo;
}

bool f(u64 n) {
  if(n == 2) { return false; }
  if(n % 2 == 0) { return true; }
  for(u64 b=2; b<n; b*=2) {
    u64 pa = n - b;
    for(u64 a=1, mul=3; mul<=pa; ++a, mul*=3) {
      u64 p = g(pa, a);
      if(mypow(p, a) == pa && is_probable_prime(p)) { return true; }
    }
  }
  return false;
}

int main(void) {
  int Q; scanf("%d", &Q);
  for(int loop=0; loop<Q; ++loop) {
    u64 n; scanf("%llu", &n);
    bool able = f(n);
    puts(able ? "Yes" : "No");
  }
  return 0;
}