#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long LL;
const LL Mod = 998244353;
typedef __int128 BIG;
vector< LL > pp, p;
vector< LL > C;
inline LL mul(LL a,LL b,LL mod){return (BIG)a*b%mod;}
LL Pow(LL a,LL b,LL mod)
{
	LL res=1;
	while(b)
	{
		if(b&1)res=mul(res,a,mod);
		a=mul(a,a,mod);
		b>>=1;
	}
	return res;
}
mt19937 rnd(time(0));
LL Make(LL l,LL r){return rand()%(r-l+1)+l;}
bool Miller_Rabin(LL n)
{
	if(n<=3)return n!=1;
	LL r=(n-1),c=0;
	while(r%2==0)r/=2,c++;
	for(int t=1;t<=3;t++)
	{
		LL a=Make(2,n-1);
		LL x=a,y=Pow(a,r,n);
		for(int i=1;i<=c;i++)
		{
			x=mul(y,y,n);
			if(x==1&&y!=1&&y!=n-1)return 0;
			y=x;
		}
		if(y!=1)return 0;
	}
	return 1;
}
LL c,mod;
LL f(LL x)
{
	return (mul(x,x,mod)+c)%mod;
}
LL gcd(LL a,LL b)
{
	if(!b)return a;
	return gcd(b,a%b);
}
LL Pollard_Rho(LL n)
{
	if(n%2==0)return 2ll;
	c=Make(2,n-1);mod=n;
	LL a=Make(2,n-1),b=1;
	for(int i=1;;i<<=1)
	{
		a=b;
		LL res=1;
		for(int j=1;j<=i;j++)
		{
			b=f(b);
			res=mul(res,abs(a-b),mod);
			if(j%127==0)
			{
				LL d=gcd(res,n);
				if(d>1)return d;
			}
		}
		LL d=gcd(res,n);
		if(d>1)return d;
	}
	return Pollard_Rho(n);
}
void resolve(LL n)
{
	if(n==1)return;
	if(Miller_Rabin(n))
	{
	//	cout << n << endl;
	    pp.pb(n);
		return;
	}
	LL x=Pollard_Rho(n);
	while(n%x==0)n/=x;
	resolve(x);
	resolve(n);
}
LL res;
bool vis[100];
LL Power(LL x, LL y) {
	LL res = 1LL, k = x % mod;
	while(y) {
		if(y & 1) res = res * k % mod;
		y >>= 1;
		k = k * k % mod;
	}
	return res;
}
LL tims;
void get(int len) {
	LL tmp = 1LL; int o = 0;
	LL ct = 0;
	for(int i = 0; i < len; i ++ ) {
		if(p[i] == mod) {
			if(!vis[i]) ct += C[i];
			else ct += C[i] - 1LL;
			continue;
		}
		if(!vis[i]) {
			tmp = tmp * Power(1LL * p[i], 1LL * C[i]);
		}
		else {
			tmp = tmp * Power(1LL * p[i], 1LL * C[i] - 1LL);
			o ++;
		}
	}
//	cout << "GGGH" << tmp << ' ';
	if(tmp % Mod == 0) {
		while(tmp % Mod == 0 && tmp) ct ++, tmp /= Mod;
	}
//	cout << tmp << endl;
	if(o & 1) tmp = Power(tmp, Mod - 2LL), ct = -ct;
	if(tmp) res = res * tmp % Mod; 
	tims += ct;
}
void dfs(int x, int et) {
	if(x == et) {
		get(et);
		return ;
	}
	vis[x] = 0;
	dfs(x + 1, et);
	vis[x] = 1;
	dfs(x + 1, et);
}
void solve(LL n) {
	pp.clear(); p.clear(); C.clear(); res = 1LL;
	tims = 0;
	resolve(n);
	sort(pp.begin(), pp.end());
	for(int i = 0; i < pp.size(); i ++ ) {
		if(i == 0 || pp[i] != pp[i - 1]) p.pb(pp[i]);
	}
	for(int i = 0; i < p.size(); i ++ ) {
		LL tmp = n; LL cnt = 0;
		while(tmp % p[i] == 0 && tmp) {
			cnt ++; tmp /= p[i];
		}
		C.pb(cnt);
	}
//	for(int i = 0; i < p.size(); i ++ ) {
//		cout << "OOO" << p[i] << ' ' << C[i] << endl;
//	}
	int sz = p.size();
	dfs(0, sz);
//	cout << tims << endl;
	if(tims != 0) puts("0");
	else printf("%lld ", res);
}
int T;
int main()
{
//	resolve(1532812);
	scanf("%d", &T);
	while(T -- ) {
		LL n; scanf("%lld", &n);
		solve(n);
	}
	return 0;
}
/*
998244353

1
26952597531
*/