#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define repeat(i, n) for (int i = 0; (i) < int(n); ++(i)) #define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i)) #define repeat_reverse(i, n) for (int i = (n)-1; (i) >= 0; --(i)) #define repeat_from_reverse(i, m, n) for (int i = (n)-1; (i) >= int(m); --(i)) #define whole(x) begin(x), end(x) #define unittest_name_helper(counter) unittest_ ## counter #define unittest_name(counter) unittest_name_helper(counter) #define unittest __attribute__((constructor)) void unittest_name(__COUNTER__) () using ll = long long; using namespace std; template ll binsearch(ll l, ll r, UnaryPredicate p) { // [l, r), p is monotone assert (l < r); -- l; while (r - l > 1) { ll m = (l + r) / 2; (p(m) ? r : l) = m; } return r; // = min { x in [l, r) | p(x) }, or r } ll powint(ll x, int y) { ll z = 1; for (ll i = 1; i <= y; i <<= 1) { if (y & i) z *= x; x *= x; } return z; } unittest { assert (powint(3, 5) == 243); assert (powint(7, 3) == 343); } ll iroot(ll n, int k) { ll y = binsearch(0, n + 1, [&](ll x) { if (n * 1.1 < pow(x, k)) return true; return n <= powint(x, k); }); if (n < powint(y, k)) -- y; return y; } unittest { repeat_from (a, 2, 100) { repeat_from (b, 1, 4) { ll c = iroot(a, b); assert (powint(c, b) <= a); assert (a < powint(c + 1, b)); } } } ll powmod(ll x, ll y, ll p) { // O(log y) assert (0 <= x and x < p); assert (0 <= y); ll z = 1; for (ll i = 1; i <= y; i <<= 1) { if (y & i) z = z * x % p; x = x * x % p; } return z; } template bool is_prime(ll n, int iteration, Generator & gen) { // miller-rabin primality test, O(k log n) assert (0 <= n); if (n == 2) return true; if (n == 1 or n % 2 == 0) return false; const ll d = (n-1) >> __builtin_ctzll(n-1); // remove trailing zeros uniform_int_distribution dist(1, n-2); // [l, r] repeat (dummy, iteration) { ll a = dist(gen); ll t = d; ll y = powmod(a, t, n); while (t != n-1 and y != 1 and y != n-1) { y = y * y % n; t *= 2; } if (y != n-1 and t % 2 == 0) return false; } return true; } bool is_prime(ll n) { static default_random_engine engine = default_random_engine(random_device()()); return is_prime(n, 20, engine); } bool solve(ll n) { // fprintf(stderr, "n = %lld\n", n); if (n >= 2 and n % 2 == 0) return true; // Goldbach's conjecture for (ll pa = 2; ; pa *= 2) { ll qb = n - pa; if (qb <= 1) break; repeat_from (b, 1, 64) { ll q = iroot(qb, b); // fprintf(stderr, "qb = %lld, b = %d -> q = %lld\n", qb, b, q); if (qb == powint(q, b) and is_prime(q)) return true; } } return false; } int main() { int q; scanf("%d", &q); while (q --) { ll n; scanf("%lld", &n); bool result = solve(n); printf("%s\n", result ? "Yes" : "No"); // fprintf(stderr, "%s\n", result ? "Yes" : "No"); } return 0; }