#include <bits/stdc++.h>
using namespace std;
int main() {
  vector<int> rs(1001, 0);
  for (int i = 2; i <= 1000; ++i) {
    if (i * i > 1000) break;
    if (rs[i]) continue;
    for (int j = i * i; j <= 1000; j += i) {
      rs[j] = i;
    }
  }
  int T;
  cin >> T;
  for (int t = 1; t <= T; ++t) {
    int n;
    cin >> n;
    vector<int> vi(n);
    map<int, int> mp;
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
      cin >> vi[i];
      if (!mp.count(rs[vi[i]])) {
        mp[rs[vi[i]]] = ++cnt;
        vi[i] = cnt;
      } else
        vi[i] = mp[rs[vi[i]]];
    }
    cout << cnt << endl;
    for (int i = 0; i < n; ++i) {
      cout << vi[i] << " ";
    }
    cout << endl;
  }
  return 0;
}
