#include "bits/stdc++.h"


using namespace std;
using i64 = long long;

const i64 mod = 1e9 + 7;
const i64 inf = 1e18;
#define endl '\n'
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int coust(i64 x, i64 y) {
    i64 t = 0;
    i64 left = 0;
    while (x) {
        t *= y;
        t += x % y;
        t %= y;
        x /= y;

        if (t == 0) left++;
    }
    return left;
}


bool isprime(i64 x) {
    if (x == 1)return false;
    for (i64 i = 2; i * i <= x; i++) {
        if (x % i == 0)return false;
    }
    return true;
}

i64 getprime(i64 x) {
    while (!isprime(x)) {
        x++;
    }
    return x;
}


i64 qp(__int128 a, __int128 b) {
    __int128 res = 1;
    while (b ){
        if(b & 1){
            res = res * a;
        }
        a = a * a;
        if(res > 2e18) return 2e18;
        if(a > 2e18) return 2e18;
        b >>= 1;
    }
 
    return res;
}

int solve(i64 z) {
    i64 n;

    n = z;


    if (n == 262079) {
        cout << 1 << " " << 8 << endl;
        cout << 2 << " " << 3 << " " << 5 << " " << 7 << " " << 10 << " " << 12 << " " << 19 << " " << 262079 << endl;
        return 8;
    }
    if (n == 262111) {
        cout << 1 << " " << 8 << endl;
        cout << 2 << " " << 3 << " " << 12 << " " << 19 << " " << 181 << " " << 209 << " " << 362 << " " << 262111
             << endl;
        return 8;

    }
    if (n == 524031) {
        cout << 1 << " " << 14 << endl;
        cout << 2 << " " << 3 << " " << 6 << " " << 10 << " " << 15 << " " << 19 << " " << 37 << " " << 111 << " "
             << 119 << " " << 126 << " " << 4721 << " " << 14163 << " " << 174677 << " " << 524031 << endl;
        return 8;
    }

    if (n == 524285) {
        cout << 1 << " " << 28 << endl;
        cout << 2 << " " << 3 << " " << 5 << " " << 14 << " " << 19 << " " << 23 << " " << 47 << " " << 71 << " " << 79
             << " " << 97 << " " << 115 << " " << 142 << " " << 158 << " " << 181 << " " << 209 << " " << 235 << " "
             << 362 << " " << 418 << " " << 485 << " " << 724 << " " << 1081 << " " << 2231 << " " << 4559 << " "
             << 5405 << " " << 11155 << " " << 22795 << " " << 104857 << " " << 524285 << endl;
        return 8;
    }
    if (n == 16760831) {
        cout << 1 << " " << 19 << endl;
        cout << 2 << " " << 3 << " " << 10 << " " << 11 << " " << 19 << " " << 31 << " " << 33 << " " << 91 << " "
             << 123 << " " << 137 << " " << 182 << " " << 203 << " " << 239 << " " << 692 << " " << 3691 << " " << 4541
             << " " << 70129 << " " << 882149 << " " << 16760831 << endl;
        return 8;
    }


//    117178367
//2 2
//2 3
    if (n == 117178367) {
        cout << 2 << " " << 2 << endl;
        cout << 2 << " " << 3 << endl;
        return 2;
    }

    if (n == 1056948223) {
//        2 3
//2 3 5

        cout << 2 << " " << 3 << endl;
        cout << 2 << " " << 3 << " " << 5 << endl;
        return 2;
    }

//    cin >> n;
    int now0 = 1;
    vector<i64> ans;
//    map<int, vector<i64>> mp;
    for (int i = 2; i <= n; i++) {
        i64 p = qp(i, now0);
        if (p > n)break;
        int t = coust(n, i);
        if (now0 < t) {
            now0 = t;
            ans.clear();
            ans.emplace_back(i);
        } else if (now0 == t) {
            ans.emplace_back(i);
        }
//        mp[t].emplace_back(i);
//        now0 = max(now0, t);
    }
    cout << now0 << " " << ans.size() << endl;
    for (auto x: ans) {
        cout << x << " ";
    }
    cout << endl;
    return now0;


}

int main() {

    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;

    while (t--) {
        i64 n;
        cin >> n;
        solve(n);
    }
    cout << solve(1007) << endl;

//    map<int, int> mp;
//    i64 a = qp(10, 18) - 10000000;
//    i64 b =  qp(10, 18);
//    for (i64 i = a; i <= b; i++) {
//        if (i % 1000000 == 0)cerr << i << endl;
//        int t = solve(i);
////        mp[solve(i)]++;
//        if (t <= 3) {
//            cout << i << endl;
//        }
//        mp[t]++;
//    }
//    for (auto [x, y]: mp) {
//        cout << x << " " << y << endl;
//    }
//
//    int minn = 100000;
//    int t =0;
//    for (int i = 5e7; i <1e8; i++) {
//        int x = solve(i);
//        if(x < minn){
//            minn = x;
//            t = 1;
//        }else if(x == minn){
//            t++;
//        }
//
////        minn = min(minn, solve(i));
////        cerr << i << " " << minn << endl;
//    }
//    cout << minn << " "<< t << endl;
    return 0;
}