1846E2 AC

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vi = vector<int>;
using ull = unsigned long long;
using ld = long double;

// constexpr ll p1 = (1ll << 50) - 51, p2 = (1ll << 50) - 117;
constexpr ll p1 = (1ll << 30) - 35, p2 = (1ll << 30) - 41;

ll fpow(ll b, ll p, ll m)
{
    ll ret = 1;
    ll cur = b;
    while (p) {
        if (p % 2)
            ret = ret * cur % m;
        cur = cur * cur % m;
        p /= 2;
    }
    return ret;
}

int main(int argc, char **argv)
{
    ll t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        bool ok = false;
        for (ll p = 3; p <= 90 && !ok; ++p) {
            ll lb = powl(n, 1.0 / (p - 1));
            auto fmod = [p](ll k) {
                return pll{(fpow(k, p, p1) + p1 - 1) % p1 * fpow(k - 1, p1 - 2, p1) % p1,
                           (fpow(k, p, p2) + p2 - 1) % p2 * fpow(k - 1, p2 - 2, p2) % p2};
            };
            if (fmod(lb) == pll{n % p1, n % p2})
                ok = true;
            else
                dbg(lb, p, n, fmod(lb), n % p1, n % p2);
        }
        cout << (ok ? "YES" : "NO") << endl;
    }
    return 0;
};