#include <iostream>
#include <vector>

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroui-loops")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
#pragma GCC optimize("vpt")
#pragma GCC optimize("rename-registers")
#pragma GCC optimize("move-loop-invariants")
#pragma GCC optimize("unswitch-loops")
#pragma GCC optimize("function-sections")
#pragma GCC optimize("data-sections")
#pragma GCC optimize("branch-target-load-optimize")
#pragma GCC optimize("branch-target-load-optimize2")
#pragma GCC optimize("btr-bb-exclusive")

using namespace std;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

void dfs(int v, int color, vector<int> &prev, vector<int> &used, vector<vector<int>> &adj, vector<vector<bool>> &matr) {
    for (int u : adj[v]) {
        if (used[u] == 0) {
            bool f = false;
            for (int g : prev) {
                if (!matr[g][u]) f = true;
            }
            if (f) continue;
            prev.push_back(u);
            used[u] = color;
            dfs(u, color, prev, used, adj, matr);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    int t; cin >> t;
    cout << gcd(437, 391) << endl;
    for (int temp = 0; temp < t; temp++) {
        int n; cin >> n;
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
        vector<vector<int>> adj(n, vector<int>());
        vector<vector<bool>> matr(n, vector<bool>(n, false));
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (gcd(nums[i], nums[j]) > 1) {
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                    matr[i][j] = matr[j][i] = true;
                }
            }
        }
        vector<int> used(n, 0);
        int color = 0;
        for (int i = 0; i < n; i++) {
            if (used[i] == 0) {
                color++;
                used[i] = color;
                vector<int> prev;
                dfs(i, color, prev, used, adj, matr);
            }
        }
        cout << color << endl;
        for (int i = 0; i < n; i++) {
            cout << used[i] << ' ';
        }
        cout << endl;
    }
}