#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef unsigned long long ull;

const int N = 8, N2 = N*N;
const int dx[] = {0, -1, 0, 1, 0};
const int dy[] = {0, 0, -1, 0, 1};

int gauss(int n, ull a[], ull b[]) {
	for(int i = 0; i < n; ++i) {
		b[i] |= 1ull<<i;
	}
	for(int k = 0; k < n; ++k) {
		int r = k, c = k;
		bool flag = true;
		for(int i = k; flag && i < n; ++i) {
			for(int j = k; flag && j < n; ++j) {
				if(a[i]>>j&1) flag = false, r = i, c = j;
			}
		}
		if(flag) return k;
		if(c != k) {
			for(int i = 0; i < n; ++i) {
				if((a[i]>>k&1) != (a[i]>>c&1)) {
					a[i] ^= 1ull<<k | 1ull<<c;
				}
			}
		}
		if(r != k) {
			swap(a[k], a[r]);
			swap(b[k], b[r]);
		}
		for(int i = 0; i < n; ++i) {
			if(i != k && (a[i]>>k&1)) {
				a[i] ^= a[k];
				b[i] ^= b[k];
			}
		}
	}
	return n;
}

ull a[N+1][N2], v[N+1][N2];
int T, r[N+1];

int main() {
	for(int n = 1; n <= 8; ++n) {
		int n2 = n*n;
		for(int i = 0; i < n; ++i) {
			for(int j = 0; j < n; ++j) {
				int x = i*n+j;
				for(int k = 0; k < 5; ++k) {
					int ni = i+dx[k];
					int nj = j+dy[k];
					if(ni >= 0 && ni < n && nj >= 0 && nj < n) {
						int y = ni*n+nj;
						a[n][x] |= 1ull<<y;
					}
				}
			}
		}
		r[n] = gauss(n2, a[n], v[n]);
	}
	scanf("%d", &T);
	while(T--) {
		int n, n2;
		ull b = 0;
		scanf("%d", &n);
		n2 = n*n;
		for(int x, i = 0; i < n; ++i) {
			scanf("%d", &x);
			b |= (ull)x<<i*n;
		}
		int m = n2-r[n], ans = 0;
		if(!m) {
			for(int i = 0; i < n2; ++i) {
				ans += __builtin_parityll(v[n][i]&b);
			}
		} else {
			for(int i = r[n]; !ans && i < n2; ++i) {
				if(__builtin_parityll(v[n][i]&b)) ans = -1;
			}
			if(!ans) {
				ans = n2;
				for(ull x = 0; x < 1ull<<m; ++x) {
					int cnt = __builtin_popcountll(x);
					for(int i = 0; cnt < ans && i < r[n]; ++i) {
						cnt += __builtin_parityll(a[n][i]>>r[n]&x) ^ __builtin_parityll(v[n][i]&b);
					}
					ans = min(ans, cnt);
				}
			}
		}
		printf("%d\n", ans);
	}
}