#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
#define ll long long
const __int128 ONE=1;

typedef __int128_t lll;
const int CNT = 12;
int P[CNT] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
const int N = 100000;
bitset <N> vis;
void prework() {
    vis.set();
    vis[0] = vis[1] = 0;
    for (int i = 2; i < N; ++i)
        for (int j = i * 2; j < N; j += i)
            vis[j] = 0;
}
ll qpow(ll a, ll p, ll mod) {
    ll ans = 1;
    for (; p; p >>= 1, a = (lll) a * a % mod)
        if (p & 1) ans = (lll) ans * a % mod;
    return ans;
}
bool MillerRabin(ll n) {
    if (n < N) return vis[n];
    ll p = n - 1, c = 0;
    while (~p & 1) p >>= 1, c++;
    for (int i = 0; i < CNT; ++i) {
        ll a = qpow(P[i], p, n);
        if (a == 1 || a == n - 1) continue;
        for (int t = 1; t <= c - 1; ++t) {
            a = (lll) a * a % n;
            if (a == n - 1) break;
        }
        if (a != n - 1) return 0;
    }
    return 1;
}

const ll I=1e18+10;
ll mu(ll a,ll b){
    if(a<=I/b)return a*b;
    return I;
}
ll qpow(ll a,ll b){
    ll c=1;
    for(;b;b>>=1){
        if(b&1)c=mu(a,c);
        if(c>=I)return I;
        a=mu(a,a);
    }
    return c;
}
void sol(){
    ll n;scanf("%lld",&n);
    if(n==1){printf("1 ");return;}
    for(int k=60;k;k--){
        ll l=1,r=1e18,e=0;
        while(l<=r){
            ll mi=(l+r)>>1;
            if(qpow(mi,k)<=n)e=mi,l=mi+1;
            else r=mi-1;
        }
        if(qpow(e,k)==n){
            if(MillerRabin(e)){printf("%lld ",e%mod);return;}
            printf("1 ");return;
        }
    }
}
int main(){
    prework();
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}