#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using uint = unsigned int; using ll = long long; using ull = unsigned long long; constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); } template using V = vector; template using VV = V>; struct rng { struct A { int n; const bool operator!=(A r) { return n != r.n; } A& operator++() { n++; return *this; } int operator*() { return n; } }; int l, r; rng(int r) : l(0), r(max(0, r)) {} rng(int l, int r) : l(l), r(max(l, r)) {} A begin() { return A{l}; } A end() { return A{r}; } }; template T pow(T x, ll n, T r) { while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; } template T pow(T x, ll n) { return pow(x, n, T(1)); } template T pow_mod(T x, ll n, T md) { T r = 1; while (n) { if (n & 1) r = (r*x)%md; x = (x*x)%md; n >>= 1; } return r % md; } bool isPrime(ll n) { if (n <= 1) return false; if (n == 2) return true; if (n % 2 == 0) return false; ll d = n-1; while (d % 2 == 0) d /= 2; // vector alist{2,3,1662803}; // n < 1.12e12 vector alist{2,3,5,7,11,13,17,19,23,29,31,37}; // n < 2^64 for (ll a: alist) { if (n <= a) break; ll t = d; ll y = pow_mod<__int128>(a, t, n); //over while (t != n-1 && y != 1 && y != n-1) { y = __int128(y)*y % n; //flow t <<= 1; } if (y != n-1 && t % 2 == 0) { return false; } } return true; } bool ck2(ll x) { for (int i = 2; i < 100; i++) { ll y = ll(pow(x, 1.0/i) + 0.01); if (!isPrime(y)) continue; ll z = 1; for (int j: rng(i)) z *= y; if (z == x) return true; } return false; } bool check(ll x) { if (x % 2 == 0) return true; ll b = 2; while (b < x) { if (ck2(x-b)) return true; b *= 2; } return false; } int main() { cin.tie(0); ios::sync_with_stdio(false); cout << setprecision(20); int q; cin >> q; for (int i: rng(q)) { ll x; cin >> x; if (check(x)) cout << "Yes" << endl; else cout << "No" << endl; } return 0; }