// clang-format off #include using namespace std; using ll = int64_t; using ld = long double; #define FOR(i, m, n) for(int i = (m); i < (n); ++i) #define FORR(i, m, n) for(int i = (m)-1; i >= (n); --i) #define rep(i, n) FOR(i, 0, n) #define repn(i, n) FOR(i, 1, n+1) #define repr(i, n) FORR(i, n, 0) #define repnr(i, n) FORR(i, n+1, 1) #define all(s) (s).begin(), (s).end() template bool chmax(T &a, const U b) { return a < b ? a = b, true : false; } template bool chmin(T &a, const U b) { return b < a ? a = b, true : false; } template istream &operator>>(istream &is, vector &v) { for (T &i : v) is>>i; return is; } template ostream &operator<<(ostream &os, const vector &v) { for (auto it=v.begin(); it!=v.end(); ++it) { os<<(it==v.begin()?"":" ")<<*it; } return os; } template void co(Head&& head, Tail&&... tail) { if constexpr(sizeof...(tail)==0) cout<(tail)...); } template void ce(Head&& head, Tail&&... tail) { if constexpr(sizeof...(tail)==0) cerr<(tail)...); } template auto make_vector(T x, int arg, Args ...args) { if constexpr(sizeof...(args)==0) return vector(arg, x); else return vector(arg,make_vector(x, args...)); } void sonic() { ios::sync_with_stdio(false); cin.tie(nullptr); } void setp(const int n) { cout << fixed << setprecision(n); } constexpr int64_t INF = 1000000000000000003; constexpr int Inf = 1000000003; constexpr int MOD = 1000000007; constexpr int MOD_N = 998244353; constexpr double EPS = 1e-7; const double PI = acos(-1); struct prime_number { const int sz = 1 << 22; bitset<1 << 22> is_not_prime; vector data; prime_number() { init(); } void init() { is_not_prime[0] = is_not_prime[1] = true; for (int i = 2; i < sz; ++i) { if (!is_not_prime[i]) { data.emplace_back(i); if ((int64_t)i * i >= sz) continue; for (int j = i * i; j < sz; j += i) { is_not_prime[j] = true; } } } } bool is_prime(int64_t n) { assert(n >= 0); if (n < sz) return !is_not_prime[n]; for (auto i : data) { if ((int64_t)i * i > n) break; if (n % i == 0) return false; } return true; } vector prime_numbers(int x) { vector res; for (int i = 2; i <= x; ++i) { if (is_prime(i)) res.emplace_back(i); } return res; } // 素因数分解 template vector> prime_factorization(T x) { if (x == 1) return vector>(1, {1, 1}); vector> res; for (auto i : data) { int cnt = 0; for (; x % i == 0; x /= i) cnt++; if (cnt) res.emplace_back(i, cnt); if ((int64_t)i * i > x) break; } if (x != 1) res.emplace_back(x, 1); return res; } // 約数列挙 template vector divisors(T x) { auto v = prime_factorization(x); vector res, a, b, cp; res.emplace_back(1); for (auto p : v) { int n = res.size(); cp.resize(n); copy(res.begin(), res.end(), cp.begin()); a.resize(n); T t = 1; for (int k = 0; k < p.second; ++k) { t *= p.first; for (int i = 0; i < n; ++i) a[i] = cp[i] * t; merge(res.begin(), res.end(), a.begin(), a.end(), back_inserter(b)); swap(res, b); b.clear(); } } return res; } // 因数分解列挙 template vector> factorization(T x) { vector> res; auto f = [&](auto self, vector v, T a) -> void { if (a == 1) res.emplace_back(v); for (auto i : divisors(a)) { if (i == 1 || (!v.empty() && v.back() > i)) continue; v.emplace_back(i); self(self, v, a / i); v.pop_back(); } }; f(f, vector(), x); return res; } }; prime_number pn; // clang-format on int main(void) { int t; cin >> t; vector>> vv; vv.resize(10000); FOR(i, 2, 10000) { vv[i] = pn.prime_factorization((ll)i); } rep(_, t) { ll x; cin >> x; auto v = pn.prime_factorization(x); unordered_map mp; ll s = 1; for (auto p : v) { mp[p.first] = p.second; s *= p.second + 1; } FOR(i, 2, 10000) { auto u = vv[i]; auto np = mp; for (auto p : u) { np[p.first] += p.second; } ll t = 1; for (auto p : np) { t *= p.second + 1; } if (s * 2 == t) { co(x * i); break; } } } return 0; }