#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;

const int MAXN = 1000000;

vector<int> primes;
bool is_prime[MAXN+1];
vector<int> prime_index_map;

void sieve(int n) {
    memset(is_prime, true, sizeof(is_prime));
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (long long j = (long long)i*i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

vector<int> get_primes_up_to(int n) {
    vector<int> res;
    for (int p : primes) {
        if (p > n) break;
        res.push_back(p);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    sieve(MAXN);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        if (n == 2) {
            cout << "2\n";
        } else if (n == 4) {
            cout << "2 3\n";
        } else if (n == 6) {
            cout << "2 3 5\n";
        } else {
            vector<int> selected;
            vector<int> odd_weight_set;
            int square_count = 0;
            vector<bool> in_odd_set(n+1, false);
            for (int i = 1; i <= n; i++) {
                int temp = i;
                int kernel = 1;
                int weight = 0;
                for (int p : primes) {
                    if (p * p > temp) break;
                    if (temp % p == 0) {
                        int cnt = 0;
                        while (temp % p == 0) {
                            cnt++;
                            temp /= p;
                        }
                        if (cnt % 2 == 1) {
                            kernel *= p;
                            weight++;
                        }
                    }
                }
                if (temp > 1) {
                    kernel *= temp;
                    weight++;
                }
                if (kernel == 1) {
                    continue;
                }
                if (weight % 2 == 1) {
                    odd_weight_set.push_back(i);
                    in_odd_set[i] = true;
                }
            }
            if (odd_weight_set.size() >= n/2) {
                for (int i = 0; i < n/2; i++) {
                    if (i > 0) cout << " ";
                    cout << odd_weight_set[i];
                }
                cout << '\n';
            } else {
                set<int> selected_set(odd_weight_set.begin(), odd_weight_set.end());
                vector<int> squares;
                for (int i = 1; i*i <= n; i++) {
                    squares.push_back(i*i);
                }
                int added_squares = 0;
                for (int sq : squares) {
                    if (selected_set.size() >= n/2) break;
                    if (added_squares < 2) {
                        selected_set.insert(sq);
                        added_squares++;
                    }
                }
                for (int i = 1; i <= n; i++) {
                    if (selected_set.size() >= n/2) break;
                    if (in_odd_set[i] || selected_set.count(i)) continue;
                    int temp = i;
                    int kernel = 1;
                    int weight = 0;
                    for (int p : primes) {
                        if (p * p > temp) break;
                        if (temp % p == 0) {
                            int cnt = 0;
                            while (temp % p == 0) {
                                cnt++;
                                temp /= p;
                            }
                            if (cnt % 2 == 1) {
                                kernel *= p;
                                weight++;
                            }
                        }
                    }
                    if (temp > 1) {
                        kernel *= temp;
                        weight++;
                    }
                    if (weight % 2 == 0 && kernel != 1) {
                        selected_set.insert(i);
                    }
                }
                vector<int> output_vec(selected_set.begin(), selected_set.end());
                for (int i = 0; i < n/2; i++) {
                    if (i > 0) cout << " ";
                    cout << output_vec[i];
                }
                cout << '\n';
            }
        }
    }
    return 0;
}