#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll mod = 998244353;
ll mult(ll a, ll b) {
    return (1LL * (a % mod) * (b % mod)) % mod;
}
ll sub(ll a, ll b) {
    ll s = (a - b) % mod;
    if (s < 0) s += mod;
    return s;
}
ll sum(ll a, ll b) {
    ll s = (a + b) % mod;
    if (s < 0) s += mod;
    return s;
}
ll pw(ll a, ll b) {
    if (b == 0) return 1;
    if (b & 1) return mult(a, pw(a, b - 1));
    ll res = pw(a, b / 2);
    return mult(res, res);
}
ll n;
const ll INF = (ll)2e18 + 10;
ll safe_mult(ll a, ll b) {
    if (!a || !b) return 0;
    if (a >= (INF + b - 1) / b) return INF;
    return a * b;
}
ll safe_pw(ll a, ll b) {
    if (b == 0) return 1;
    if (b & 1) return safe_mult(safe_pw(a, b - 1), a);
    ll res = safe_pw(a, b / 2);
    return safe_mult(res, res);
}
typedef long long lint;
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;
        return 1;
    }
}
int T = 0;
vector<ll> A;
void solve() {
    cin >> n;
    if (n == 1) {
//        cout << 1;
        A.emplace_back(1);
        return;
    }
    for (ll k = 63; k >= 1; k--) {
        ll L = 1;
        ll R = n + 1;
        while (R - L > 1) {
            ll mid = (L + R) / 2;
            if (safe_pw(mid, k) <= n) L = mid;
            else R = mid;
        }
        if (safe_pw(L, k) == n) {
            if (miller_rabin::isprime(L)) {
                A.emplace_back(L % mod);
                ++T;
                return;
            }
            A.emplace_back(1);
            return;
        }
    }
    assert(false);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    int tst;
    cin >> tst;
    for (int i = 1; i <= tst; i++) {
        solve();
    }
    cout << T << '\n';
    for (int i = 0; i < tst; i++) {
        if (i != 0) {
            cout << " ";
        }
        cout << A[i];
    }
    return 0;
}