#include <bits/stdc++.h>

using namespace std;

const int MaxN = (int)5e1 + 10;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;

int n, a[MaxN];
int who[MaxN];

int getWho(int v) {
	return v == who[v] ? v : who[v] = getWho(who[v]);
}

void solve() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		who[i] = i;
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			if (__gcd(a[i], a[j]) == 1) {
				who[getWho(i)] = getWho(j);
			}
		}
	}
	int cnt = 0;
	for (int i = 1; i <= n; ++i) {
		cnt += getWho(i) == i;
	}
	if (cnt == 1) {
		cout << "0\n";
	} else {
		cout << "1\n";
		bool yeah = false;
		for (int i = 1; i <= n; ++i) {
			if (a[i] != 29) {
				yeah = true;
			}
		}
		if (yeah) {
			a[n] = 29;
		} else {
			a[n] = 31;
		}
	}
	for (int i = 1; i <= n; ++i) {
		who[i] = i;
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			if (__gcd(a[i], a[j]) == 1) {
				who[getWho(i)] = getWho(j);
			}
		}
	}
	cnt = 0;
	for (int i = 1; i <= n; ++i) {
		cnt += getWho(i) == i;
	}
	assert (cnt == 1);
	for (int i = 1; i <= n; ++i) {
		cout << a[i] << (i == n ? '\n' : ' ');
	}
}

int main() {
//	freopen("input.txt", "w", stdout);
	int t;
	scanf("%d", &t);
	while (t --> 0) {
		solve();
	}
	return 0;
}