#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
int fx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
int fy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int kx[] = {1, 1, 2, 2, -1, -1, -2, -2};
int ky[] = {2, -2, 1, -1, 2, -2, 1, -1};
bool mark[10002];
vector<int> primes;
vector<int> G[10002];
int parent[10002];
int POS[10002];
void reset() {
  for (int i = 0; i < 10001; i++) {
    parent[i] = i;
    G[i].clear();
    POS[i] = 0;
  }
}
void gen() {
  for (long long i = 2; i < 10001; i++) {
    if (!mark[i]) {
      primes.push_back(i);
      for (long long j = i * i; j < 10001; j += i) {
        mark[j] = 1;
      }
    }
  }
}
int Find(int x) {
  if (x == parent[x]) return x;
  return parent[x] = Find(parent[x]);
}
void Union(int u, int v) {
  int p = Find(u);
  int q = Find(v);
  if (p != q) parent[q] = p;
}
void check(int n, int pos) {
  for (int x : primes) {
    if (n % x == 0) {
      if (!G[x].size()) {
        G[x].push_back(pos);
      } else {
        int u = G[x][0];
        Union(u, pos);
      }
      break;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  gen();
  int T;
  cin >> T;
  while (T--) {
    reset();
    int n;
    cin >> n;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++) {
      cin >> v[i];
      check(v[i], i);
    }
    vector<int> ans(n + 1);
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
      int p = Find(i);
      if (!POS[p]) {
        POS[p] = ++cnt;
      }
      ans[i] = POS[p];
    }
    cout << cnt << "\n";
    for (int i = 1; i <= n; i++) cout << ans[i] << " ";
    cout << "\n";
  }
  return 0;
}
