#pragma GCC target("avx2") //#pragma GCC target("avx") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma GCC optimize("O3") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") // #include // #include #include // #include // #include #include #include #include // #include #include #include #include #include #include #include #include #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include #include // #include // #include // #include // #include // #include // #include // #include // #include using namespace std; #include using namespace atcoder; #define STRINGIFY(n) #n #define TOSTRING(n) STRINGIFY(n) using ll = long long; using ull = unsigned long long; template using maxque = priority_queue; template using minque = priority_queue,greater>; #define int ll #define endl "\n" #define unless(cond) if(!(cond)) #define until(cond) while(!(cond)) #define rep(i,s,e) for(ll i = (s); i < (e); ++i) #define repR(i,s,e) for(ll i = (e)-1; (s) <= i; --i) #define repE(i,s,e) for(ll i = (s); i <= (e); ++i) #define repER(i,s,e) for(ll i = (e); (s) <= i; --i) #define repSubsetR(set,super) for(ll _super=super,set = _super; 0 <= set; --set)if(set &= _super, true) #define ALL(xs) begin(xs), end(xs) #define ALLR(xs) rbegin(xs), rend(xs) #define ALLC(xs) cbegin(xs), cend(xs) #define ALLCR(xs) crbegin(xs), crend(xs) template void uniq(C &xs){ xs.erase(unique(ALL(xs)), xs.end()); } template constexpr ll len(C &&xs){ return size(forward(xs)); } ll BIT(ll n){ return 1LL< "; } template void debug_(const X &x, const Xs&... xs){ cerr << x; (void)initializer_list{ (cerr << ", " << xs,0)... };cerr << endl; }void debug_(){ cerr << endl; } #define ASSERT(pred,...) (static_cast(pred) ? void(0) : (debug_h(__FILE__, __LINE__, "ASSERT FAIL! " #pred "; " #__VA_ARGS__),debug_(__VA_ARGS__),exit(1))) template X &&dbg_(X &&x){ cerr<(x); } #ifdef DEBUG #define dbg(x) (debug_h(__FILE__, __LINE__, "" #x),dbg_(x)) #define debug(...) (debug_h(__FILE__, __LINE__, "" #__VA_ARGS__),debug_(__VA_ARGS__)) #define clk(...) (cerr << __VA_ARGS__ " @ " << (clock()-clock0) < decltype(*this); using SELF_ = decltype(((self_fn_*)nullptr)()); DEF_ORD(==) DEF_ORD(!=) DEF_ORD(<) DEF_ORD(>) DEF_ORD(<=) DEF_ORD(>=) template auto operator<<(ostream &out, const C &xs) -> enable_if_t, char*> && !is_same_v, string>, decltype(begin(xs),out)&> { out<<"[ "; for(auto&&x:xs)out< auto operator>>(istream &in, C &xs) -> enable_if_t, char*> && !is_same_v, string>, decltype(begin(xs),in)&> { for(auto&x:xs)in>>x; return in; } template void print_tuple_(ostream &out, Tuple const &xs, std::index_sequence){ out << "("; (void)initializer_list{ (out << (I==0?"":", ") << std::get(xs),0)... }; out << ")"; } template ostream &operator<<(ostream &out, tuple const &xs){ print_tuple_(out, xs, make_index_sequence()); return out; } template void read_tuple_(istream &in, Tuple &xs, std::index_sequence){ (void)initializer_list{ (in >> std::get(xs),0)... }; } template istream &operator>>(istream &in, tuple &xs){ read_tuple_(in, xs, make_index_sequence()); return in; } template ostream &operator<<(ostream &out, pair const &p){ return out << "(" << p.first << ", " << p.second << ")"; } template istream &operator>>(istream &in, pair &p){ return in >> p.first >> p.second; } template> ostream &operator<<(ostream &out, MINT x){ return out << x.val(); } template> istream &operator>>(istream &in, MINT &x){ ll a; in>>a; x = a; return in; } template struct Fix : F { template Fix(G &&g) : F{forward(g)} {} template decltype(auto) operator()(Xs&&... xs)const{ return F::operator()(*this, forward(xs)...); } }; template Fix(F&&) -> Fix>; template bool chmin(T &a, U b){ if(a <= b)return false; a = b; return true; } template bool chmax(T &a, U b){ if(a >= b)return false; a = b; return true; } //const signed MOD = 998244353; const signed MOD = 1000000007; // 10^9+7 using mint = static_modint; // using mint = dynamic_modint<-1>; // mint::set_mod(mod); // using mint0 = dynamic_modint<0>; // mint0::set_mod(mod); const ll INF = BIT(60); ll solve(){ vector primes; map p2i; vector lpf(316230, -1); rep(d, 2, len(lpf)){ if(lpf[d] == -1){ lpf[d] = d; p2i[d] = len(primes); primes.push_back(d); } for(auto p : primes){ unless(p <= lpf[d] && p * d < len(lpf)) break; lpf[p * d] = p; } } auto maxp = primes[8]; map, signed> memo; auto ans = [&](map nu){ auto it = memo.find(nu); unless(it == memo.end()) return it->second; for(ll i=2;;++i){ ll j = i; ll prod = 1,div = 1; auto nu2 = nu; until(j <= 1){ ll p = lpf[j]; div *= nu2[p]+1; j /= p; ++nu2[p]; prod *= nu2[p]+1; } if(prod == 2 * div) return memo[nu] = (signed)i; } }; ll t;cin>>t; rep(i,0,t){ ll xx;cin>>xx;ll x=xx; debug(x); map nu; unless(x