#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
#define db double
#define pii pair<int,int>
#define endl "\n"

using namespace std;

void solve()
{
    int n; cin >> n;
    vector<int> color(n + 1, 0);
    color[1] = 1;

    for (int i = 2; i <= n; i++)
    {
        if (color[i] == 0)
            color[i] = 2;
            
        for (int j = 2 * i; j <= n; j += i)
            if (color[j] < color[i] + 1)
                color[j] = color[i] + 1;
    }

    cout << *max_element(color.begin(), color.end()) << endl;
    for (int i = 1; i <= n; i++)
        cout << color[i] << " ";
    cout << endl;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T; cin >> T;
    while (T--)
        solve();

    return 0;
}