#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
using bigint = long long int;
using vi = vector<int>;
using vll = vector<long long int>;
int spf[2005];
void smallestFactor() {
  for (int i = 1; i <= 2000; i++) spf[i] = i;
  for (int i = 2; i * i <= 2000; i++) {
    if (spf[i] == i) {
      for (int j = i * i; j <= 2000; j += i) {
        if (spf[j] == j) spf[j] = i;
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  smallestFactor();
  int T;
  cin >> T;
  while (T--) {
    int N;
    cin >> N;
    int arr[N + 1];
    for (int i = 0; i < N; i++) {
      int x;
      cin >> x;
      arr[i] = spf[x];
    }
    map<int, int> m;
    int j = 1;
    vi ans;
    for (int i = 0; i < N; i++) {
      if (m.find(arr[i]) != m.end())
        ans.push_back(m[arr[i]]);
      else {
        m[arr[i]] = j;
        ans.push_back(j);
        j++;
      }
    }
    cout << j - 1 << "\n";
    for (int x : ans) cout << x << " ";
    cout << "\n";
  }
  return 0;
}
