#include <bits/stdc++.h>
using namespace std;
bool sortinrev(long long x, long long y) { return x > y; }
void swap(long long* a, long long* b) {
  long long temp = *a;
  *a = *b;
  *b = temp;
}
long long div_ceil(long long a, long long b) { return (a + b - 1) / b; }
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a / gcd(a, b)) * b; }
const int MOD = 1000 * 1000 * 1000 + 7;
const long long INF = 1e18L + 5;
const int nax = 4000005;
const int N = int(1e6);
void solve() {
  long long n;
  cin >> n;
  vector<long long> c(n, -1);
  vector<long long> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
  vector<long long> arr(n);
  for (long long i = 0; i < n; ++i) {
    cin >> arr[i];
  }
  long long p = 1, cnt = 1;
  for (long long i = 0; i < 11; i++) {
    bool flag = 0;
    for (long long j = 0; j < n; j++) {
      if (c[j] == -1 && gcd(arr[j], primes[i]) > 1) {
        c[j] = cnt;
        flag = 1;
      }
    }
    if (flag) cnt++;
  }
  cout << *max_element((c).begin(), (c).end()) << "\n";
  for (auto x : c) cout << x << " ";
  cout << "\n";
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  cerr << "\nI am Winning";
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}
