D_Carousel.cpp

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> v(n);
    bool flag = 0;
    for(int i=0;i<n;i++) {
        cin >> v[i];
        if(v[i] != v[0]) flag = 1;
    }
    if(flag == 0) {
        cout << "1\n";
        for(int i=0;i<n;i++) cout << "1 "; cout << "\n";
        return;
    }
    if(n % 2 == 0) {
        cout << "2\n";
        for(int i=0;i<n;i+=2) cout << "1 2 "; cout << "\n";
        return;
    }
    int pos = -1;
    for(int i=0;i<n;i++) {
        if(v[i] == v[(i+1) % n]) {
            pos = i;
            break;
        }
    }
    if(pos == -1) {
        cout << "3\n";
        for(int i=0;i<n-1;i+=2) cout << "1 2 "; cout << "3\n";
        return;
    }
    cout << "2\n";
    int curr = 1;
    for(int i=0;i<n;i++) {
        cout << curr << " ";
        if(i != n-1 && i == pos) {
            cout << curr << " ";
            i++;
        }
        curr = 3 - curr;
    }
    cout << "\n";

}


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

    int _;
    cin >> _;
    while (_-->0) {
        solve();
    }

    return 0;
}