#include <bits/stdc++.h>
using namespace std;
vector<int> factors(int x) {
  vector<int> r;
  for (int i = 2; i * i <= x; ++i) {
    if (x % i == 0) r.push_back(i);
    while (x % i == 0) x /= i;
  }
  if (x != 1) r.push_back(x);
  return r;
}
int isprime(int x) { return factors(x).size() == 1; }
void solve() {
  int n;
  cin >> n;
  vector<int> v(n);
  for (int& x : v) cin >> x;
  map<int, int> m;
  for (int i = 2; i <= 31; ++i)
    if (isprime(i)) m[i] = 1;
  vector<vector<int>> p(32);
  for (int i = 0; i < n; ++i) {
    for (int u : factors(v[i])) {
      if (m.count(u)) {
        p[u].push_back(i);
      }
    }
  }
  int c = 0;
  vector<int> res(n);
  for (int i = 0; i < 32; ++i) {
    if (p[i].size()) {
      int ok = 0;
      ++c;
      for (int u : p[i]) {
        if (!res[u]) {
          res[u] = c;
          ok = 1;
        }
      }
      if (!ok) c--;
    }
  }
  cout << c << '\n';
  for (int& x : res) cout << x << ' ';
  cout << '\n';
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) solve();
}
