#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b){
return (b == 0)? a: gcd(b, a%b);
}
int main()
{
int t;
cin>>t;
while(t--){
long long n;
cin>>n;
vector<long long> v(n), co(n);
for(int x = 0; x <n; x++)
cin>>v[x];
int cnt = 0;
for(int x = 0; x< n; x++){
if(co[x]) continue;
for(int y = x; y < n; y++){
if(!co[y] && gcd(v[x], v[y]) > 1)
co[y] = cnt;
}
co[x] = ++cnt;
}
cout<<cnt<<endl;
for(int i = 0; i < n; i++){
cout<<co[i]<<" ";
}
cout<<endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmxvbmcgbG9uZyBnY2QobG9uZyBsb25nIGEsIGxvbmcgbG9uZyBiKXsKCXJldHVybiAoYiA9PSAwKT8gYTogZ2NkKGIsIGElYik7Cn0KaW50IG1haW4oKQp7CglpbnQgdDsKCWNpbj4+dDsKCXdoaWxlKHQtLSl7CgkJbG9uZyBsb25nIG47CgkJY2luPj5uOwoJCXZlY3Rvcjxsb25nIGxvbmc+IHYobiksIGNvKG4pOwoJCWZvcihpbnQgeCA9IDA7IHggPG47IHgrKykKCQkJY2luPj52W3hdOwoJCWludCBjbnQgPSAwOwoJCWZvcihpbnQgeCA9IDA7IHg8IG47IHgrKyl7CgkJCWlmKGNvW3hdKSBjb250aW51ZTsKCQkJZm9yKGludCB5ID0geDsgeSA8IG47IHkrKyl7CgkJCQlpZighY29beV0gJiYgZ2NkKHZbeF0sIHZbeV0pID4gMSkKCQkJCQljb1t5XSA9IGNudDsKCQkJfQoJCQljb1t4XSA9ICsrY250OwoJCX0KCQljb3V0PDxjbnQ8PGVuZGw7CgkJZm9yKGludCBpID0gMDsgaSA8IG47IGkrKyl7CgkJCWNvdXQ8PGNvW2ldPDwiICI7CgkJfQoJCWNvdXQ8PGVuZGw7Cgl9CgoJcmV0dXJuIDA7Cn0K