#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 1e9 + 7;
void solve() {
  long long int n, a;
  cin >> n;
  vector<long long int> v;
  vector<long long int> col(35, -1);
  vector<long long int> ans(n + 2, 0);
  for (long long int i = 0; i < n; i++) {
    cin >> a;
    v.push_back(a);
  }
  long long int val = 1;
  for (long long int i = 0; i < n; i++) {
    if (v[i] % 2 == 0) {
      if (col[2] == -1) {
        col[2] = val;
        val++;
      }
      ans[i] = col[2];
    } else if (v[i] % 3 == 0) {
      if (col[3] == -1) {
        col[3] = val;
        val++;
      }
      ans[i] = col[3];
    } else if (v[i] % 5 == 0) {
      if (col[5] == -1) {
        col[5] = val;
        val++;
      }
      ans[i] = col[5];
    } else if (v[i] % 7 == 0) {
      if (col[7] == -1) {
        col[7] = val;
        val++;
      }
      ans[i] = col[7];
    } else if (v[i] % 11 == 0) {
      if (col[11] == -1) {
        col[11] = val;
        val++;
      }
      ans[i] = col[11];
    } else if (v[i] % 13 == 0) {
      if (col[13] == -1) {
        col[13] = val;
        val++;
      }
      ans[i] = col[13];
    } else if (v[i] % 17 == 0) {
      if (col[17] == -1) {
        col[17] = val;
        val++;
      }
      ans[i] = col[17];
    } else if (v[i] % 19 == 0) {
      if (col[19] == -1) {
        col[19] = val;
        val++;
      }
      ans[i] = col[19];
    } else if (v[i] % 23 == 0) {
      if (col[23] == -1) {
        col[23] = val;
        val++;
      }
      ans[i] = col[23];
    } else if (v[i] % 29 == 0) {
      if (col[29] == -1) {
        col[29] = val;
        val++;
      }
      ans[i] = col[29];
    } else if (v[i] % 31 == 0) {
      if (col[31] == -1) {
        col[31] = val;
        val++;
      }
      ans[i] = col[31];
    }
  }
  long long int mx = -1;
  for (long long int i = 0; i < n; i++) {
    mx = max(mx, ans[i]);
  }
  cout << mx << endl;
  for (long long int i = 0; i < n; i++) {
    cout << ans[i] << " ";
  }
  cout << endl;
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long int t;
  cin >> t;
  while (t--) solve();
  return 0;
}
