#include <bits/stdc++.h>
using namespace std;
int t, n, a[1000], b[1000], m, x, y;
int main() {
  scanf("%d", &t);
  for (; t--;) {
    m = y = 0;
    int c[1000]{};
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
      scanf("%d", a + i);
      for (int j = 2; j * j <= a[i]; j++) {
        if (a[i] % j == 0) {
          b[i] = j;
          if (j > m) {
            y = m = j;
          }
          c[j]++;
          break;
        }
      }
    }
    for (int i = 1; i <= m; i++) {
      if (!c[i]) {
        x = i + 1;
        while (!c[x] && x <= m) x++;
        for (int j = 0; j < n; j++) {
          if (b[j] == x) {
            y = b[j] = i;
          }
        }
        c[x] = 0;
      }
    }
    printf("%d\n", y);
    for (int i = 0; i < n; i++) {
      printf("%d ", b[i]);
    }
    puts("");
  }
}
