Khi biểu diễn dãy số thành một đồ thị một chiều, với mỗi phần tử là một node và cạnh ~(u, v)~ biểu diễn cho quan hệ ~v~ chia hết cho ~u~, ta sẽ nhận thấy độ cao của đồ thị, hay là đường đi dài nhất trong đồ thị, sẽ là đáp án của đề bài dựa trên định lý Dirichlet.

Đây cũng là nền tảng cho Định lý Dilworth.

#include <bits/stdc++.h>

using namespace std;

template<typename T>
void println(vector<T> v) {
    for(int x: v) {
        cout << x << " ";
    }
    cout << endl;
}

template<typename... Args>
void println(Args... args) {
    (cout << ... << args) << endl;
}

void solve() {
    int n; cin >> n;

    vector<int> c(n, -1);

    int cnt = 0;
    int sum = 0;
    while (sum < n) {
        int k = 1<<cnt;
        for(int i = sum; i < min(n, sum+k); ++i) {
            c[i] = cnt+1;
        }
        sum += k;
        cnt++;
    }

    println(cnt);
    println(c);
}

int main() {
    int n_test;
    cin >> n_test;

    for(int i_test = 1; i_test <= n_test; ++i_test) solve();

    return 0;
}