NIGERIAN

#include <bits/stdc++.h>

using namespace std;

int main()
{   vector<int> prime ={2,3,5,7,11,13,17,19,23,29,21};

    int t; cin >> t;

    while(t--){
        int n; cin >> n;
        vector<int> num[n];
        vector<int> color(n, 0);
        for (auto& numi : num) cin >> numi;

        int colused = 1;
        for(int i=0;i<11;i++){
            int cnt = 0;
            for(int j = 0;j<n;j++){
                if(color[j] == 0 && num[j]%prime[i] == 0){
                    cnt++;
                    color[i] = colused;
                }
            }
            if(cnt!=0){
                colused++;
            }
        }
        cout << colused - 1 << endl;
        for(int i = 0;i<n;i++){
            cout << color[i] << " ";
        }
        cout << endl;
    }

    return 0;
}