#include using namespace std; #define all(a) (a).begin(), (a).end() using ll = long long; using ull = unsigned long long; using vll = vector; ull bit(int n) { return 1ull << n; } ll sign(ll a) { return (a > 0) - (a < 0); } ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); } ll cdiv(ll a, ll b) { return -fdiv(-a, b); } template using priority_queue_rev = priority_queue, greater>; template T sq(const T &a) { return a * a; } template bool chmax(T &a, const U &b) { return ((a < b) ? (a = b, true) : (false)); } template bool chmin(T &a, const U &b) { return ((a > b) ? (a = b, true) : (false)); } template ostream &operator<<(ostream &os, const vector &a) { os << "("; for (auto itr = a.begin(); itr != a.end(); itr++) { os << *itr << (next(itr) != a.end() ? ", " : ""); } os << ")"; return os; } #ifdef ONLINE_JUDGE #define dump(...) (void(0)) #else void debug() { cerr << endl; } template void debug(Head &&head, Tail &&... tail) { cerr << head; if (sizeof...(Tail)) cerr << ", "; debug(tail...); } #define dump(...) cerr << __LINE__ << ": " << #__VA_ARGS__ << " = ", debug(__VA_ARGS__) #endif struct rep { struct itr { int v; itr(int v) : v(v) {} void operator++() { ++v; } int operator*() const { return v; } bool operator!=(const itr &i) const { return v != i.v; } }; int l, r; rep(int r) : l(min(0, r)), r(r) {} rep(int l, int r) : l(min(l, r)), r(r) {} itr begin() const { return l; }; itr end() const { return r; }; }; struct per { struct itr { int v; itr(int v) : v(v) {} void operator++() { --v; } int operator*() const { return v; } bool operator!=(const itr &i) const { return v != i.v; } }; int l, r; per(int r) : l(min(0, r)), r(r) {} per(int l, int r) : l(min(l, r)), r(r) {} itr begin() const { return r - 1; }; itr end() const { return l - 1; }; }; struct multi_prime_factorize { std::vector spf; multi_prime_factorize(int n) : spf(n + 1) { std::iota(spf.begin(), spf.end(), 0LL); for (int i = 2; i * i <= n; i++) { if (spf[i] < i) { continue; } for (int j = i * i; j <= n; j += i) { if (spf[j] == j) { spf[j] = i; } } } } std::vector prime_factorize(int a) { std::vector ret; while (a > 1) { ret.emplace_back(spf[a]); a /= spf[a]; } return ret; } }; template ll binry_search(ll ok, ll ng, F is_ok) { while (abs(ok - ng) > 1) { ll mid = (ok + ng) / 2; (is_ok(mid) ? ok : ng) = mid; } return ok; } std::vector get_prime_table(int n) { std::vector ret(n + 1, true); if (n >= 0) { ret[0] = false; } if (n >= 1) { ret[1] = false; } for (int i = 2; i * i <= n; i++) { if (!ret[i]) { continue; } for (int j = i << 1; j <= n; j += i) { ret[j] = false; } } return ret; } int main() { multi_prime_factorize mpf(1e5); ll t; cin >> t; while (t--) { ll k; cin >> k; cout << binry_search(1e18, 0, [&](ll y) { ll j = 2; ll cnt = 1; while (true) { ll rrt = (ll)pow(y, 1.0 / j); ll rt = binry_search(max(1ll, rrt - 2), rrt + 2, [&](ll x) { ll cur = 1; for (ll i : rep(j)) { if (x > y / cur) return false; cur *= x; } return true; }); if (rt == 1) break; auto v = mpf.prime_factorize(j); for (ll i : rep(v.size() - 1)) { if (v[i] == v[i + 1]) rt = 1; } cnt += (rt - 1) * ((v.size() & 1) ? 1 : -1); j++; } return cnt >= k; }) << endl; } }