#include #include using namespace std; using namespace atcoder; #define rep(i, n) for(int i=0;i<(n);++i) #define rep1(i, n) for(int i=1;i<=(n);i++) #define ll long long using mint = modint998244353; using P = pair; using lb = long double; using T = tuple; #ifdef LOCAL # include # define dbg(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else # define dbg(...) (static_cast(0)) #endif int main() { int q; cin >> q; vector A(q); rep(i,q) cin >> A[i]; ll x = 1e12; map mp; for(int j=2;j<=45;j++) { ll now = 2; while(true) { ll nxt = 1; rep(k,j) nxt*=now; if(nxt>x) break; mp[nxt] = j; now++; } } rep(i,q) { if(mp[A[i]]==0) { cout<<1<