#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target( \
    "avx,avx2,fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
long long MOD = 1e18;
long long INF = 1e18;
const int N = 200005;
const int NN = 2400005;
vector<pair<long long, vector<long long> > > x;
map<vector<long long>, long long> mp;
void dfs(vector<long long> nw) {
  sort(nw.begin(), nw.end());
  if (mp.count(nw)) return;
  mp[nw] = 1;
  long long sm = 0;
  for (int i = 0; i < 5; i++) {
    sm += nw[i];
  }
  x.push_back({sm, nw});
  for (int i = 0; i < 5; i++) {
    if (nw[i] + 1 <= 5) {
      nw[i]++;
      dfs(nw);
      nw[i]--;
    }
  }
}
map<vector<long long>, long long> ans;
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0),
      cout << fixed << setprecision(20);
  long long t;
  cin >> t;
  while (t--) {
    long long n;
    cin >> n;
    vector<long long> a(n);
    map<long long, vector<long long> > mp;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      for (int j = 2; j * j <= a[i]; j++) {
        if (a[i] % j == 0) {
          mp[j].push_back(i);
          break;
        }
      }
    }
    vector<long long> ans(n);
    long long k = 0;
    for (auto i : mp) {
      k++;
      for (auto j : i.second) {
        ans[j] = k;
      }
    }
    cout << k << "\n";
    for (auto i : ans) {
      cout << i << " ";
    }
    cout << "\n";
  }
}
