Untitled

#include <bits/stdc++.h>

#include <cmath>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iomanip>
#pragma GCC optimize("Ofast")

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define allof(x) x, x + (sizeof(x) / sizeof(x[0]))
#define endl '\n'
#define int ll
#define pop_cnt(x) (__builtin_popcountll(x))
#define LSB(x) (__builtin_ffsll(x) - 1)
#define MSB(x) (64 - __builtin_clzll(x) - 1)

using namespace std;
using namespace __gnu_pbds;

void file(string s = "me") {
#ifdef DEBUG
    freopen("me.in", "r", stdin);
    freopen("me.out", "w", stdout);
#else
    if (s != "me") {
        freopen((s + ".in").c_str(), "r", stdin);
        freopen((s + ".out").c_str(), "w", stdout);
    }
#endif
}

template <typename dt>
using oset = tree<dt, null_type, less<dt>, rb_tree_tag,
                  tree_order_statistics_node_update>;
// find_by_order(k), order_of_key(k)

#ifdef DEBUG
#include "debug\debug.hpp"
#else
#define debug(...)
#define debug_itr(...)
#define debug_bits(...)
#define debug_pq(...)
#define debug_q(...)
#endif

#define PI 3.14159265358979323846

// using L = __int128;
// loop to 4 get only NSWE

const int dx[]{0, 1, 0, -1, -1, -1, 1, 1};
const int dy[]{1, 0, -1, 0, -1, 1, -1, 1};

const ll INF = 1E18 + 5, N = 1E6 + 1, MOD = 1E9 + 7;

const int MAXN = 3E5 + 5;
bitset<MAXN + 1> is_prime;


void sieve() {
    is_prime.set();
    is_prime[0] = is_prime[1] = 0;  
    for (int i = 2; i * i <= MAXN; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= MAXN; j += i) {
                is_prime[j] = 0;
            }
        }
    }
}



void solve() {
    ll n;
    cin >> n;
    vector<int> color(n + 1, -1);
    color[1] = 1;
    vector<ll> primes;
    for(int i = 0; i <= (1LL << (MSB(n)) + 1); i++){
        if(is_prime[i]) primes.push_back(i);
    }
    debug_itr(all(primes));

    vector<set<ll>> graph(n + 1);
    for(auto prime: primes){
        for(int v = 1; v <= n; v++){
            ll u = (prime ^ v);
            if (0 < u && u <= n && u != v) {
                graph[u].insert(v);
                graph[v].insert(u);
            }
        }
    }
    
    vector<vector<ll>> adj(n + 1);
    for(int i = 1; i <= n; i++){
        for(auto u: graph[i]) adj[i].push_back(u);
    }
    int max_color = 1;
    queue<int> q;
    q.push(1);
    vector<bool> vis(n + 1, false);
    vis[1] = true; 
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        set<int> used_colors;
        for (int v : graph[u]) {
            if (color[v] != -1) {
                used_colors.insert(color[v]);
            } else if(!vis[v]) {
                vis[v] = true; 
                q.push(v);
            }
        }

        int c = 1;
        while (used_colors.find(c) != used_colors.end()) {
            c++;
        }
        
        color[u] = c;
        max_color = max(max_color, c);
    }

    cout << max_color << endl;
    for (int i = 1; i <= n; i++) {
        cout << color[i] << " \n"[i == n];
    }

}


int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    file();
    sieve();
    int T = 1;
    cin >> T;
    for (int TT = 1; TT <= T; TT++) {
        solve();
    }
    cout.flush();
    return 0;
}