#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;
}