CF1846E2 TLE

#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;

// 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 <= 95 && !ok; ++p) {
            int lb = 2, ub = 1e9;
            // auto f = [p](ll k) { return (pow(double(k), double(p)) - 1) / (double) (k - 1); };
            auto f = [p](ll k) { return (powl(k, p) - 1) / (k - 1); };
            while (lb + 1 < ub) {
                ll mid = (lb + ub) / 2;
                if (f(mid) <= n)
                    lb = mid;
                else
                    ub = mid;
            }
            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;
        }
        /*
        for (ll k = 2; k * k < n; ++k) {
            int lb = 3, ub = 21;
            auto f = [k](ll p) { return (powl(k, p) - 1) / (k - 1); };
            while (lb + 1 < ub) {
                ll mid = (lb + ub) / 2;
                if (f(mid) <= n)
                    lb = mid;
                else
                    ub = mid;
            }
            if (f(lb) == n) {
                ok = true;
                break;
            }
        }
        */
        cout << (ok ? "YES" : "NO") << endl;
    }
    return 0;
};