#include<bits/stdc++.h>
#define irep(i,l,r) for(int i = l; i <= r; ++i)
#define drep(i,r,l) for(int i = r; i >= l; --i)
#define ceil(pp,qq) (((pp)>0)^((qq)>0)?-Abs(pp)/Abs(qq):(pp)%(qq)?(pp)/(qq)+1:(pp)/(qq))
#define floor(pp,qq) (((pp)>0)^((qq)>0)?-ceil(abs(pp),abs(qq)):(pp)/(qq))
#define ll long long
#define lint long long
#define LL __int128
using namespace std;
ll Abs(ll x){return x > 0 ? x : - x;}
inline ll read(){
	char ch = getchar();
	ll s = 0; bool w = 0;
	while(!isdigit(ch)){if(ch == '-')w = 1;ch = getchar();}
	while(isdigit(ch))s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
	return w ? - s : s;
}

const int itinf = 2e9;
const ll llinf = 4e18;
const int mod = 998244353;
const int N = 500009;

ll qpow(LL a, ll b, LL md){
	LL ans = 1;
	while(b){
		if(b & 1)ans *= a, ans %= md;
		a *= a, a %= md, b >>= 1;
	}
	return ans;
}

namespace miller_rabin{
    lint mul(lint x, lint y, lint mod){ return (__int128) x * y % mod; }
    lint ipow(lint x, lint y, lint p){
        lint ret = 1, piv = x % p;
        while(y){
            if(y&1) ret = mul(ret, piv, p);
            piv = mul(piv, piv, p);
            y >>= 1;
        }
        return ret;
    }
    bool miller_rabin(lint x, lint a){
        if(x % a == 0) return 0;
        lint d = x - 1;
        while(1){
            lint tmp = ipow(a, d, x);
            if(d&1) return (tmp != 1 && tmp != x-1);
            else if(tmp == x-1) return 0;
            d >>= 1;
        }
    }
    bool isprime(lint x){
        for(auto &i : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}){
            if(x == i) return 1;
            if(x > 40 && miller_rabin(x, i)) return 0;
        }
        if(x <= 40) return 0;
        for (int it = 0; it < 20; it++) {
            ll f = rand() % (x - 1) + 1;
            if (miller_rabin(x, f)) return 0;
        }
        return 1;
    }
}
using namespace miller_rabin;
int isp[1000999] = {1,1};
vector<ll>pri;
set<ll>avl;
map<ll,ll>mp;
int main(){
	srand(time(0));
	ll pmax = 1000000;
	for(int i = 2; i <= pmax; ++ i){
		if(! isp[i])pri.push_back(i);
		for(int p : pri){
			if(1ll * i * p > pmax)break;
			isp[i * p] = 1;
		}
	}
	
	for(LL p : pri){
		for(LL t0 = p; t0 <= llinf; t0 *= p){
			avl.insert(t0);
			mp[t0] = p;
		}
	}

	int T = read();
	while(T --){
		ll n = read();
		
		if(isprime(n)){
			printf("%lld ", n % mod);
			continue;
		}
		
		ll k = sqrt(n);
		if((k + 1) * (k + 1) == n) ++ k;
		if(k * k == n){
			if(isprime(k)){
				printf("%lld ", k % mod);
				continue;
			}

		}
		if(avl.find(n) == avl.end())printf("1 ");
		else printf("%lld ",(mp[n]) % mod);
	}
	
	return 0;
}