#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const ll mod = 998244353;

ll modpow(ll b, ll e)
{
    ll ans = 1;
    for (; e; b = b * b % mod, e /= 2)
        if (e & 1)
            ans = ans * b % mod;
    return ans;
}

typedef unsigned long long ull;
ull modmul(ull a, ull b, ull M)
{
    ll ret = a * b - M * ull(1.L / M * a * b);
    return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull modpow(ull b, ull e, ull mod)
{
    ull ans = 1;
    for (; e; b = modmul(b, b, mod), e /= 2)
        if (e & 1)
            ans = modmul(ans, b, mod);
    return ans;
}

bool isPrime(ull n)
{
    if (n < 2 || n % 6 % 4 != 1)
        return (n | 1) == 3;
    ull A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},
        s = __builtin_ctzll(n - 1), d = n >> s;
    for (ull a : A)
    { // ^ count trailing zeroes
        ull p = modpow(a % n, d, n), i = s;
        while (p != 1 && p != n - 1 && a % n && i--)
            p = modmul(p, p, n);
        if (p != n - 1 && i != s)
            return 0;
    }
    return 1;
}

ull pollard(ull n)
{
    auto f = [n](ull x)
    { return modmul(x, x, n) + 1; };
    ull x = 0, y = 0, t = 30, prd = 2, i = 1, q;
    while (t++ % 40 || __gcd(prd, n) == 1)
    {
        if (x == y)
            x = ++i, y = f(x);
        if ((q = modmul(prd, max(x, y) - min(x, y), n)))
            prd = q;
        x = f(x), y = f(f(y));
    }
    return __gcd(prd, n);
}

vector<ull> factor(ull n)
{
    if (n == 1)
        return {};
    if (isPrime(n))
        return {n};
    ull x = pollard(n);
    auto l = factor(x), r = factor(n / x);
    l.insert(l.end(), all(r));
    return l;
}

void solve()
{
    ll n;
    cin >> n;

    vector<ull> f = factor(n);
    // calculate product of (n/d)^(mobius(d))
    // only calculate d subset of prime factors
    set<ull> st;
    for (ull i : f)
        st.insert(i);

    vector<ull> v(st.begin(), st.end());
    int m = v.size();

    ll p = 1, q = 1;
    ll pc = 0, qc = 0;
    for (int i = 0; i < (1 << m); i++)
    {
        ll d = 1;
        int mob = 1;
        for (int j = 0; j < m; j++)
        {
            if (i & (1 << j))
            {
                d *= v[j];
                mob *= -1;
            }
        }

        ll nd = n / d;
        if (mob == 1)
        {
            while ((nd % mod) == 0)
            {
                nd /= mod;
                pc++;
            }
            p = (p * (nd % mod)) % mod;
        }
        else if (mob == -1)
        {
            while ((nd % mod) == 0)
            {
                nd /= mod;
                qc++;
            }
            q = (q * (nd % mod)) % mod;
        }
    }

    ll mn = min(pc, qc);
    pc -= mn;
    qc -= mn;

    if (pc > 0) {
        cout << "0 ";
    } else {
        cout << p * modpow(q, mod - 2) % mod << ' ';
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}