Chef has a pepperoni pizza in the shape of a $N \times N$ grid; both its rows and columns are numbered $1$ through $N$. Some cells of this grid have pepperoni on them, while some do not. Chef wants to cut the pizza vertically in half and give the two halves to two of his friends. Formally, one friend should get everything in the columns $1$ through $N/2$ and the other friend should get everything in the columns $N/2+1$ through $N$.
Before doing that, if Chef wants to, he may choose one row of the grid and reverse it, i.e. swap the contents of the cells in the $i$-th and $N+1-i$-th column in this row for each $i$ ($1 \le i \le N/2$).
After the pizza is cut, let's denote the number of cells containing pepperonis in one half by $p_1$ and their number in the other half by $p_2$. Chef wants to minimise their absolute difference. What is the minimum value of $|p_1-p_2|$?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$-th of these lines contains a string with length $N$ describing the $i$-th row of the grid; this string contains only characters '1' (denoting a cell with pepperonis) and '0' (denoting a cell without pepperonis).

-----Output-----
For each test case, print a single line containing one integer — the minimum absolute difference between the number of cells with pepperonis in the half-pizzas given to Chef's friends.

-----Constraints-----
- $1 \le T \le 1,000$
- $2 \le N \le 1,000$
- $N$ is even
- the sum of $N \cdot N$ over all test cases does not exceed $2 \cdot 10^6$

-----Example Input-----
2
6
100000
100000
100000
100000
010010
001100
4
0011
1100
1110
0001

-----Example Output-----
2
0

-----Explanation-----
Example case 1: Initially, $|p_1-p_2| = 4$, but if Chef reverses any one of the first four rows from "100000" to "000001", $|p_1-p_2|$ becomes $2$.
Example case 2: Initially, $|p_1-p_2| = 0$. We cannot make that smaller by reversing any row.

Difficulty: MEDIUM_HARD
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
for _ in range(int(input())):
	N = int(input())
	reverse = [0] * N
	diff = 0
	for z in range(N):
		inp = input()
		x = y = 0
		for j in range(N):
			if inp[j] == '1':
				if j < N // 2:
					x += 1
				else:
					y += 1
		diff += x - y
		reverse[z] = -2 * (x - y)
	ans = abs(diff)
	for i in range(N):
		if abs(diff + reverse[i]) < ans:
			ans = abs(diff + reverse[i])
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	li = []
	(p1, p2, f) = (0, 0, 0)
	for i in range(n):
		l = []
		s = input()
		p1 += s.count('1', 0, n // 2)
		p2 += s.count('1', n // 2, n)
		l = list(s)
		li.append(l)
	(g, h) = (p1, p2)
	b = abs(p1 - p2)
	if abs(p1 - p2) == 0:
		print(0)
	else:
		c1 = []
		for k in li:
			for j in range(n // 2):
				if k[j] == '1' and k[n - 1 - j] == '0':
					p1 -= 1
					p2 += 1
				elif k[j] == '0' and k[n - 1 - j] == '1':
					p2 -= 1
					p1 += 1
			c1.append(abs(p1 - p2))
			(p1, p2) = (g, h)
		print(min(c1))


def row(alist):
	(a, n) = (0, len(alist))
	for i in range(n // 2):
		if alist[i] == '1':
			a += 1
	for i in range(n // 2, n):
		if alist[i] == '1':
			a -= 1
	return a
t = int(input())
for count in range(t):
	n = int(input())
	mat = [input() for i in range(n)]
	A = []
	for i in range(n):
		A.append(row(mat[i]))
	s = sum(A)
	B = [abs(s)]
	if s > 0:
		for i in range(n):
			if A[i] > 0:
				B.append(abs(s - 2 * A[i]))
	else:
		for i in range(n):
			if A[i] < 0:
				B.append(abs(s - 2 * A[i]))
	print(min(B))


tests = int(input())
for t in range(tests):
	N = int(input())
	pizl = []
	pizr = []
	diffs = []
	for i in range(N):
		p = input()
		pizl.append(p[:N // 2].count('1'))
		pizr.append(p[N // 2:].count('1'))
		diffs.append(pizl[i] - pizr[i])
	mx = abs(sum(pizl) - sum(pizr))
	for i in range(len(diffs)):
		diff = abs(sum(pizl) + 2 * pizr[i] - sum(pizr) - 2 * pizl[i])
		if diff < mx:
			mx = diff
	print(mx)


import numpy as np
for _ in range(int(input())):
	n = int(input())
	m1 = []
	m2 = []
	(c1, c2) = ([], [])
	for i in range(n):
		temp = [int(x) for x in input()]
		m1 = temp[0:n // 2]
		m2 = temp[n // 2:]
		c1.append(m1.count(1))
		c2.append(m2.count(1))
	if sum(c1) - sum(c2) == 0:
		print('0')
	else:
		ans = abs(sum(c1) - sum(c2))
		for i in range(n):
			if c1[i] != c2[i]:
				s = abs(sum(c1) - c1[i] + c2[i] - (sum(c2) + c1[i] - c2[i]))
				ans = min(s, ans)
		print(ans)


for __ in range(int(input())):
	n = int(input())
	a = []
	ans = 10 ** 9
	for _ in range(n):
		a.append(list(input()))
	(l1, l2, acnt, bcnt, diff) = ([], [], 0, 0, [])
	for i in range(n):
		(acnt, bcnt) = (0, 0)
		for j in range(len(a[i]) // 2):
			if a[i][j] == '1':
				acnt += 1
			if a[i][n - 1 - j] == '1':
				bcnt += 1
		l1.append(acnt)
		l2.append(bcnt)
	(acnt, bcnt) = (sum(l1), sum(l2))
	if acnt == bcnt:
		print('0')
	elif abs(bcnt - acnt) == 1:
		print('1')
	else:
		if bcnt > acnt:
			(l1, l2) = (l2, l1)
			(acnt, bcnt) = (bcnt, acnt)
		for i in range(n):
			val = l1[i] - l2[i]
			diff.append(val if val > 0 else 0)
		for i in range(len(diff)):
			ans = min(ans, abs(acnt - diff[i] - bcnt - diff[i]))
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	row_count = {}
	for i in range(n):
		s = input()
		row_count[i + 1] = [s[:n // 2].count('1'), s[n // 2:].count('1')]
	(left_sum, right_sum) = (0, 0)
	for val in row_count.values():
		left_sum += val[0]
		right_sum += val[1]
	min_abs_diff = abs(left_sum - right_sum)
	for (row, val) in row_count.items():
		diff_swap_row = abs(left_sum - val[0] + val[1] - (right_sum - val[1] + val[0]))
		if diff_swap_row < min_abs_diff:
			min_abs_diff = diff_swap_row
	print(min_abs_diff)


t = int(input())
for _ in range(t):
	n = int(input())
	lr = [0] * n
	for i in range(n):
		s = input()
		lr[i] = s[:n // 2].count('1') - s[n // 2:].count('1')
	lrsum = sum(lr)
	if lrsum == 0:
		print('0')
	else:
		x = [abs(lrsum - 2 * lr[i]) for i in range(n)]
		print(min(x))


t = int(input())
for i in range(t):
	diff = []
	n = int(input())
	for j in range(n):
		c1 = 0
		c2 = 0
		l1 = list(map(int, input()))
		for k in range(n):
			if l1[k] == 1 and k < n // 2:
				c1 += 1
			elif l1[k] and k >= n // 2:
				c2 += 1
		diff.append(c1 - c2)
	current_diff = sum(diff)
	new = []
	for kk in range(len(diff)):
		new.append(abs(current_diff - 2 * diff[kk]))
	print(min(min(new), abs(current_diff)))


t = int(input())
for itera in range(t):
	n = int(input())
	grid = []
	x = []
	p1_g = 0
	p2_g = 0
	for i in range(n):
		grid.append(input())
		grid[i] = list(map(int, grid[i]))
		x.append(sum(grid[i][0:n // 2]) - sum(grid[i][n // 2:n]))
	diffi = sum(x)
	if diffi > 0:
		p1_g = 1
	elif diffi < 1:
		p2_g = 1
	mini = abs(diffi)
	diffi = abs(diffi)
	if diffi != 0:
		if p1_g == 1:
			for (i, val) in enumerate(x):
				if x[i] > 0:
					if mini > abs(diffi - 2 * x[i]):
						mini = abs(diffi - 2 * x[i])
		else:
			for (i, val) in enumerate(x):
				if x[i] < 0:
					if mini > abs(diffi + 2 * x[i]):
						mini = abs(diffi + 2 * x[i])
	print(abs(mini))


for _ in range(int(input())):
	n = int(input())
	f3 = []
	for _ in range(n):
		x = input()
		f3.append(x[:n // 2].count('1') - x[n // 2:].count('1'))
	s = sum(f3)
	m = abs(s)
	for i in f3:
		m = min(m, abs(s - 2 * i))
	print(m)


T = int(input())
for _ in range(T):
	N = int(input())
	mini = 10000000
	(count1, count2) = (0, 0)
	u = []
	save = []
	for i in range(N):
		a = input()
		u.append(a)
		x = a[:N // 2].count('1')
		y = a[N // 2:].count('1')
		count1 += x
		count2 += y
		save.append(x - y)
	if count1 == count2:
		print(0)
		continue
	for i in save:
		mini = min(abs(count1 - 2 * i - count2), mini)
	print(mini)


for T in range(int(input())):
	N = int(input())
	P = [0] * N
	Q = [0] * N
	R = [0] * N
	X = N // 2
	for I in range(N):
		P[I] = input()
	for I in range(N):
		for J in range(X):
			if P[I][J] == '1':
				Q[I] += 1
			if P[I][J + X] == '1':
				R[I] += 1
	S = sum(Q) - sum(R)
	Z = {abs(S)}
	for I in range(N):
		if Q[I] != R[I]:
			Z.add(abs(S + 2 * (R[I] - Q[I])))
	print(min(Z))


import numpy as np

def program():
	n = int(input())
	Pz_list = []
	for i in range(n):
		s = input()
		L = []
		for j in range(n):
			L.append(s[j])
		Pz_list.append(L)
	Pz = np.array(Pz_list, dtype='int8')
	nh = int(n / 2)
	Pz1 = Pz[:, 0:nh]
	Pz2 = Pz[:, nh:n]
	s1 = np.sum(Pz1)
	s2 = np.sum(Pz2)
	diff = s1 - s2
	s1_row = np.sum(Pz1, axis=1)
	s2_row = np.sum(Pz2, axis=1)
	diff_row = s1_row - s2_row
	change_row = np.abs(diff - diff_row * 2)
	min_change = np.min(change_row)
	ans = min(min_change, abs(diff))
	print(ans)
T = int(input())
while T:
	program()
	T -= 1


for t in range(int(input())):
	n = int(input())
	matrix = []
	ans = 500
	p1 = 0
	p2 = 0
	diff = []
	for i in range(n):
		num = []
		a = input()
		x = 0
		y = 0
		for j in range(n // 2):
			num.append(int(a[j]))
			if a[j] == '1':
				p1 += 1
				x += 1
		for j in range(n // 2, n):
			num.append(int(a[j]))
			if a[j] == '1':
				p2 += 1
				y += 1
		diff.append(2 * (y - x))
		matrix.append(num)
	for k in range(n):
		ans = min(ans, abs(p1 - p2 + diff[k]))
	print(min(ans, abs(p1 - p2)))


t = int(input())
for _ in range(t):
	n = int(input())
	l = [0] * n
	r = [0] * n
	for i in range(n):
		s = input()
		l[i] = s[:n // 2].count('1')
		r[i] = s[n // 2:].count('1')
		if l[i] > r[i]:
			l[i] = l[i] - r[i]
			r[i] = 0
		elif l[i] == r[i]:
			l[i] = 0
			r[i] = 0
		else:
			r[i] = r[i] - l[i]
			l[i] = 0
	lsum = sum(l)
	rsum = sum(r)
	x = abs(lsum - rsum)
	if x == 0:
		print('0')
	else:
		m = 1000000000000000
		if lsum > rsum:
			for j in range(n):
				k = abs(x - 2 * l[j])
				if k < m:
					m = k
					if m == 0:
						break
		elif rsum > lsum:
			for j in range(n):
				k = abs(x - 2 * r[j])
				if k < m:
					m = k
					if m == 0:
						break
		print(m)


t = int(input())
for _ in range(t):
	n = int(input())
	l = [input() for _ in range(n)]
	(fh, sh) = (list(), list())
	(p1, p2) = (0, 0)
	for i in range(n):
		s = l[i]
		(a, b) = (s[:n // 2].count('1'), s[n // 2:].count('1'))
		p1 += a
		p2 += b
		fh.append(a)
		sh.append(b)
	d = abs(p1 - p2)
	for i in range(n):
		k = p1 - fh[i] + sh[i]
		m = p2 - sh[i] + fh[i]
		if abs(k - m) < d:
			d = abs(k - m)
	print(d)


T = int(input())
for _ in range(T):
	n = int(input())
	L = []
	M = []
	for i in range(n):
		N = list(input())
		ans1 = 0
		ans2 = 0
		for j in range(n):
			if N[j] == '1':
				if j < n // 2:
					ans1 += 1
				else:
					ans2 += 1
		M.append(ans1)
		L.append(ans2)
	ans1 = sum(M)
	ans2 = sum(L)
	if ans1 == ans2:
		print(0)
	elif ans1 > ans2:
		a = ans1 - ans2
		dif = a
		for i in range(n):
			if M[i] > L[i]:
				b = M[i] - L[i]
				if abs(a - 2 * b) < dif:
					dif = abs(a - 2 * b)
		print(dif)
	else:
		a = ans2 - ans1
		dif = a
		for i in range(n):
			if L[i] > M[i]:
				b = L[i] - M[i]
				if abs(a - 2 * b) < dif:
					dif = abs(a - 2 * b)
		print(dif)


for _ in range(int(input())):
	n = int(input())
	left = [None] * n
	right = [None] * n
	for i in range(n):
		st = input()
		left[i] = st[:n // 2].count('1')
		right[i] = st[n // 2:].count('1')
	dif = abs(sum(left) - sum(right))
	if dif == 0:
		print(0)
	else:
		for i in range(n):
			lft = list(left)
			rgt = list(right)
			t = lft[i]
			lft[i] = rgt[i]
			rgt[i] = t
			dif2 = abs(sum(lft) - sum(rgt))
			if dif2 < dif:
				dif = dif2
		print(dif)


n = lambda : map(int, input().split())
x = int(input())
for __ in range(x):
	a = int(input())
	d = []
	e = []
	for i in range(a):
		b = input()
		d.append(b[:a // 2].count('1'))
		e.append(b[a // 2:].count('1'))
	p = sum(d)
	q = sum(e)
	m = abs(p - q)
	for i in range(a):
		l = abs(p - d[i] + e[i] - (q - e[i] + d[i]))
		if l < m:
			m = l
	print(m)


t = int(input())
for you in range(t):
	n = int(input())
	lo = []
	for i in range(n):
		l = input()
		li = [int(i) for i in l]
		lo.append(li)
	lrowhalf1 = [0 for i in range(n)]
	lrowhalf2 = [0 for i in range(n)]
	for i in range(n):
		lrowhalf1[i] = sum(lo[i][0:n // 2])
		lrowhalf2[i] = sum(lo[i][n // 2:n])
	mina = abs(sum(lrowhalf1) - sum(lrowhalf2))
	for i in range(n):
		mini = abs(sum(lrowhalf1) - 2 * (lrowhalf1[i] - lrowhalf2[i]) - sum(lrowhalf2))
		if mini < mina:
			mina = mini
	print(mina)


t = int(input())
for i in range(t):
	n = int(input())
	a = []
	c1 = 0
	c2 = 0
	for i in range(n):
		s = input()
		a.append([s[0:n // 2].count('1'), s[n // 2:].count('1')])
		c1 += a[i][0]
		c2 += a[i][1]
	tp1 = c1
	tp2 = c2
	m = abs(c1 - c2)
	for i in range(n):
		tp1 += a[i][1]
		tp1 -= a[i][0]
		tp2 += a[i][0]
		tp2 -= a[i][1]
		if m > abs(tp1 - tp2):
			m = abs(tp1 - tp2)
		tp1 = c1
		tp2 = c2
	print(m)


t = int(input())
for _ in range(t):
	n = int(input())
	pizza = [None] * n
	for i in range(n):
		pizza[i] = list(map(int, list(input())))
	f1_pep = f2_pep = 0
	for i in range(n):
		for j in range(n // 2):
			if pizza[i][j] == 1:
				f1_pep += 1
	for i in range(n):
		for j in range(n // 2, n):
			if pizza[i][j] == 1:
				f2_pep += 1
	diff = abs(f1_pep - f2_pep)
	if diff == 0:
		print(0)
	else:
		for i in range(n):
			left_sum = sum(pizza[i][:n // 2])
			right_sum = sum(pizza[i][n // 2:])
			f1_pep = f1_pep - left_sum + right_sum
			f2_pep = f2_pep - right_sum + left_sum
			current_diff = abs(f1_pep - f2_pep)
			if current_diff < diff:
				diff = current_diff
			f1_pep = f1_pep + left_sum - right_sum
			f2_pep = f2_pep + right_sum - left_sum
		print(diff)


T = int(input())
for i in range(T):
	n = int(input())
	aux = [0] * n
	tot = 0
	for i in range(n):
		s = list(map(int, list(input())))
		aux[i] = sum(s[:n // 2]) - sum(s[n // 2:])
	tot = sum(aux)
	if tot == 0:
		print(0)
	else:
		x = []
		for i in range(len(aux)):
			x.append(abs(tot - 2 * aux[i]))
		print(min(x))


test = int(input())
for i in range(test):
	n = int(input())
	a = []
	p1 = p2 = 0
	for j in range(n):
		s = input()
		a.append([s[:n // 2].count('1'), s[n // 2:].count('1')])
		p1 += a[j][0]
		p2 += a[j][1]
	m = abs(p1 - p2)
	tp2 = p2
	tp1 = p1
	for j in range(n):
		tp1 -= a[j][0]
		tp1 += a[j][1]
		tp2 -= a[j][1]
		tp2 += a[j][0]
		if m > abs(tp1 - tp2):
			m = abs(tp1 - tp2)
		tp1 = p1
		tp2 = p2
	print(m)


T = int(input())
for i in range(T):
	l = []
	p1 = 0
	p2 = 0
	N = int(input())
	for j in range(N):
		s = input()
		l.append(s)
		p1 += s[:N // 2].count('1')
		p2 += s[N // 2:].count('1')
	m = abs(p1 - p2)
	for j in range(N):
		a = l[j][:(N + 1) // 2].count('1')
		b = l[j][(N + 1) // 2:].count('1')
		p_1 = p1 - a + b
		p_2 = p2 - b + a
		m = min(m, abs(p_1 - p_2))
	print(m)


import math
t = int(input())
while t > 0:
	r = []
	n = int(input())
	(c1, c2) = (0, 0)
	p = [0] * n
	q = [0] * n
	for i in range(0, n):
		r = input()
		for j in range(0, n // 2):
			if r[j] == '1':
				c1 = c1 + 1
				p[i] = p[i] + 1
			if r[n - j - 1] == '1':
				c2 = c2 + 1
				q[i] = q[i] + 1
	if c1 == c2:
		print(0)
	else:
		m = abs(c1 - c2)
		for i in range(0, n):
			m = min(m, abs(c1 - p[i] + q[i] - (c2 - q[i] + p[i])))
		print(m)
	t = t - 1


def ans(mat, n):
	(a, b) = (0, 0)
	x = n // 2
	for i in range(n):
		for j in range(n):
			if j <= x - 1:
				a += mat[i][j]
			else:
				b += mat[i][j]
	if abs(a - b) == 0:
		print(0)
		return
	ans = abs(a - b)
	for i in range(n):
		(x1, y) = (0, 0)
		for j in range(n):
			if j <= x - 1:
				x1 += mat[i][j]
			else:
				y += mat[i][j]
		ans = min(ans, abs(a + y - x1 - (b + x1 - y)))
	print(ans)
	return
for _ in range(int(input())):
	n = int(input())
	mat = []
	for _ in range(n):
		arr = [int(i) for i in input()]
		mat.append(arr)
	ans(mat, n)


T = int(input())
for i in range(T):
	N = int(input())
	t1 = []
	for i in range(N):
		s = list(map(int, input()))
		(c1, c2) = (0, 0)
		for j in range(N):
			if s[j] == 1 and j < N // 2:
				c1 += 1
			elif s[j] and j >= N // 2:
				c2 += 1
		t1.append(c1 - c2)
	t2 = sum(t1)
	r = []
	for k in range(len(t1)):
		r.append(abs(t2 - 2 * t1[k]))
	print(min(min(r), abs(t2)))


for _ in range(int(input())):
	b_left = []
	c_right = []
	d_left = []
	e_right = []
	aa = []
	a = []
	nil = int(input())
	for _ in range(nil):
		a = list(map(int, input()))
		aa.append(a)
	for ia in aa:
		b_left.append(ia[:nil // 2])
		c_right.append(ia[nil // 2:])
		d_left.append(sum(ia[:nil // 2]))
		e_right.append(sum(ia[nil // 2:]))
	max_diff = abs(sum(d_left) - sum(e_right))
	if max_diff == 0:
		print(0)
	else:
		m = 0
		for (i, j) in zip(b_left, c_right):
			if sum(i) > sum(j) or sum(j) > sum(i):
				dummy_d_left = d_left.copy()
				dummy_e_right = e_right.copy()
				ls = b_left[m]
				rs = c_right[m]
				dummy_d_left[m] = sum(rs)
				dummy_e_right[m] = sum(ls)
				if abs(sum(dummy_d_left) - sum(dummy_e_right)) < max_diff:
					max_diff = abs(sum(dummy_d_left) - sum(dummy_e_right))
			m = m + 1
		print(max_diff)


def reverse(s):
	str = ''
	for i in s:
		str = i + str
	return str
t = int(input())
for i in range(t):
	n = int(input())
	l = [None for _ in range(n)]
	p1 = 0
	p2 = 0
	for j in range(n):
		l[j] = input()
		s = l[j][0:int(n / 2)]
		s1 = l[j][int(n / 2):n]
		p1 = p1 + s.count('1')
		p2 = p2 + s1.count('1')
	smallest = abs(p1 - p2)
	for j in range(n):
		l[j] = reverse(l[j])
		p1 = 0
		p2 = 0
		for x in range(n):
			s = l[x][0:int(n / 2)]
			s1 = l[x][int(n / 2):n]
			p1 = p1 + s.count('1')
			p2 = p2 + s1.count('1')
		if abs(p1 - p2) < smallest:
			smallest = abs(p1 - p2)
		l[j] = reverse(l[j])
	print(smallest)


try:
	for _ in range(int(input())):
		n = int(input())
		(ss, a) = ([], [])
		(f, lo) = (0, 0)
		limit = int(n / 2)
		for t in range(n):
			s = input()
			ss.append(s)
			p = s[0:limit]
			f = p.count('1')
			p1 = s[limit:n]
			lo = p1.count('1')
			a.append(f - lo)
		total = sum(a)
		if total == 0:
			print(0)
		else:
			f = [abs(total - 2 * a[i]) for i in range(n)]
			print(min(f))
except:
	pass


for _ in range(int(input())):
	n = int(input())
	inp = []
	for _ in range(n):
		inp.append(list(input()))
	m = len(inp)
	n = len(inp[0])
	p1 = 0
	p2 = 0
	ar1 = []
	ar2 = []
	for i in range(m):
		left = 0
		right = 0
		for j in range(n):
			if j <= n // 2 - 1:
				if inp[i][j] == '1':
					left += 1
			elif inp[i][j] == '1':
				right += 1
		ar1.append(left)
		ar2.append(right)
	mini = abs(sum(ar1) - sum(ar2))
	if mini == 0:
		print(mini)
	else:
		for i in range(len(ar1)):
			(ar1[i], ar2[i]) = (ar2[i], ar1[i])
			minv = abs(sum(ar1) - sum(ar2))
			if minv <= mini:
				mini = minv
			(ar1[i], ar2[i]) = (ar2[i], ar1[i])
		print(mini)


for _ in range(int(input())):
	n = int(input())
	q = []
	for i in range(n):
		d = input()
		q.append(d)
	p1 = 0
	p2 = 0
	d = -1
	for i in range(n):
		p1 += q[i][:n // 2].count('1')
		p2 += q[i][n // 2:].count('1')
	w = abs(p1 - p2)
	for i in range(n):
		a = q[i][:n // 2].count('1')
		b = q[i][n // 2:].count('1')
		w = min(w, abs(p1 - 2 * (a - b) - p2))
	print(w)


from numpy import *
t = int(input())
for i in range(t):
	N = int(input())
	A = []
	for i in range(N):
		k = int(input())
		l = []
		while k > 0:
			l.insert(0, k % 10)
			k = k // 10
		while len(l) != N:
			l.insert(0, 0)
		A.append(l)
		l = []
	k = array(A)
	k1 = k[0:, 0:N // 2]
	k2 = k[0:, N // 2:]
	chetan = abs(sum(sum(k1)) - sum(sum(k2)))
	if sum(sum(k1)) - sum(sum(k2)) != 0:
		for i in range(N):
			k[i] = k[i][::-1]
			chetan = min(chetan, abs(sum(sum(k1)) - sum(sum(k2))))
			k[i] = k[i][::-1]
		print(chetan)
	else:
		print(0)


import copy
for _ in range(int(input())):
	n = int(input())
	a = []
	b = []
	c = []
	r = []
	for j in range(n):
		f = input()
		a.append(f)
		b.append(f.count('1', 0, n // 2))
		c.append(f.count('1', n // 2, n))
	s = copy.deepcopy(a)
	x = sum(b)
	y = sum(c)
	if x == y:
		print(0)
		continue
	else:
		for k in range(n):
			a = copy.deepcopy(s)
			b = []
			c = []
			a[k] = a[k][::-1]
			for j in range(n):
				b.append(a[j].count('1', 0, n // 2))
				c.append(a[j].count('1', n // 2, n))
			x = sum(b)
			y = sum(c)
			r.append(abs(x - y))
	print(min(r))


for _ in range(int(input())):
	N = int(input())
	array = []
	for i in range(N):
		a = input()
		first = 0
		second = 0
		for j in range(N // 2):
			first += int(a[j])
		for j in range(N // 2, N):
			second += int(a[j])
		array.append([first, second])
	sm1 = 0
	sm2 = 0
	for i in array:
		sm1 += i[0]
		sm2 += i[1]
	diff = abs(sm1 - sm2)
	for i in array:
		diff = min(diff, abs(sm1 - sm2 - i[0] * 2 + i[1] * 2))
	print(diff)


t = int(input())
for i in range(t):
	n = int(input())
	mat = []
	for j in range(n):
		s = list(input())
		mat.append(s)
	cnt = []
	p1 = 0
	p2 = 0
	for j in range(n):
		a = 0
		b = 0
		for k in range(len(mat[j])):
			if k < n / 2 and mat[j][k] == '1':
				a += 1
				p1 += 1
			elif k >= n / 2 and mat[j][k] == '1':
				b += 1
				p2 += 1
		cnt.append([a, b])
	minm = abs(p1 - p2)
	for i in range(n):
		minm = min(minm, abs(p1 - p2 - 2 * cnt[i][0] + 2 * cnt[i][1]))
	print(minm)


for _ in range(int(input())):
	n = int(input())
	s = []
	for i in range(n):
		s.append(input())
	l = []
	r = []
	for i in s:
		l.append(i[:n // 2].count('1'))
		r.append(i[n // 2:].count('1'))
	p = sum(l) - sum(r)
	if abs(p) <= 1:
		print(abs(p))
	else:
		x = min([abs(p - 2 * (l[i] - r[i])) for i in range(n)])
		print(x)


def get_dp(n: int, a: list) -> list:
	(lc, rc) = ([0] * n, [0] * n)
	for i in range(n):
		for j in range(n // 2):
			if a[i][j] == '1':
				lc[i] += 1
			if a[i][n - 1 - j] == '1':
				rc[i] += 1
	return [i - j for (i, j) in zip(lc, rc)]

def solve(n: int, a: list) -> int:
	diff = get_dp(n, a)
	sd = sum(diff)
	asd = abs(sd)
	for d in diff:
		nsd = sd - 2 * d
		asd = min(asd, abs(nsd))
	return asd
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	a = []
	for i in range(n):
		a.append(input().strip())
	print(solve(n, a))


def diff(k):
	if k >= 0:
		return k
	else:
		return -1 * k
t = int(input())
for _ in range(t):
	n = int(input())
	l = []
	for _ in range(n):
		s = input()
		tmp = 0
		for j in range(int(n / 2)):
			tmp += int(s[j]) - int(s[j + int(n / 2)])
		l.append(tmp)
	if sum(l) == 0:
		print(0)
	else:
		if sum(l) < 0:
			l = [-1 * i for i in l]
		tmp = sum(l)
		s = sum(l)
		for i in l:
			if diff(s - 2 * i) < tmp:
				tmp = diff(s - 2 * i)
		print(tmp)


for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		a = input()
		l.append(a)
	x = 0
	y = 0
	p = 0
	q = 0
	li = []
	for i in range(n):
		p = 0
		q = 0
		for j in range(n):
			if j < n / 2 and l[i][j] == '1':
				x += 1
				p += 1
			elif j >= n / 2 and l[i][j] == '1':
				y += 1
				q += 1
		a = []
		a = (p, q)
		li.append(a)
	mi = abs(x - y)
	if x - y == 0:
		print(x - y)
	else:
		mi = abs(x - y)
		d = x - y
		for i in range(n):
			c = x - li[i][0] + li[i][1]
			b = y + li[i][0] - li[i][1]
			z = abs(c - b)
			if mi > abs(z):
				mi = abs(z)
		print(mi)


from sys import stdin, stdout
for _ in range(int(input())):
	n = int(input())
	leftsum = []
	rightsum = []
	LEFTSUM = 0
	RIGHTSUM = 0
	halfn = int(n / 2)
	for i in range(n):
		a = input()
		leftsum.append(a[:halfn].count('1'))
		rightsum.append(a[halfn:].count('1'))
		LEFTSUM += leftsum[i]
		RIGHTSUM += rightsum[i]
	ans = 10 ** 10
	for i in range(n):
		ans = min(ans, abs(LEFTSUM - RIGHTSUM - 2 * leftsum[i] + 2 * rightsum[i]), abs(LEFTSUM - RIGHTSUM))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	(l, l1, l2, s) = ([], [], [], 0)
	for i in range(n):
		s1 = input()
		a = s1[:n // 2].count('1') - s1[n // 2:].count('1')
		l.append(a)
		s += a
	if s == 0:
		print(0)
	else:
		m = 1000000000
		for i in l:
			if abs(s - 2 * i) < m:
				m = abs(s - 2 * i)
		print(m)


t = int(input())
for i in range(t):
	n = int(input())
	(a, b) = ([], [])
	for i in range(n):
		s = input()
		(x, y) = (0, 0)
		for j in range(len(s)):
			if j < n / 2 and s[j] == '1':
				x += 1
			elif j >= n / 2 and s[j] == '1':
				y += 1
		a.append(x)
		b.append(y)
	(sa, sb) = (sum(a), sum(b))
	ans = abs(sa - sb)
	for i in range(len(a)):
		if sa > sb:
			temp = abs(sa - a[i] + b[i] - (sb + a[i] - b[i]))
			ans = min(ans, temp)
		elif sb > sa:
			temp = abs(sa + b[i] - a[i] - (sb - b[i] + a[i]))
			ans = min(ans, temp)
	print(ans)


t = int(input())
for T in range(t):
	n = int(input())
	mid = n // 2
	l1 = []
	l2 = []
	val = []
	for i in range(n):
		num = input()
		s1 = num[:mid]
		s2 = num[mid:]
		l1.append(s1.count('1'))
		l2.append(s2.count('1'))
	v1 = sum(l1)
	v2 = sum(l2)
	diff = abs(v1 - v2)
	for i in range(n):
		diff = min(diff, abs(v1 - l1[i] + l2[i] - (v2 - l2[i] + l1[i])))
	print(diff)


t = int(input())
for _ in range(t):
	n = int(input())
	p1 = p2 = 0
	pepper = []
	for i in range(n):
		pizza = input()
		left = right = 0
		for i in range(n // 2):
			if pizza[i] == '1':
				left += 1
			if pizza[n - i - 1] == '1':
				right += 1
		p1 += left
		p2 += right
		pepper.append((left, right))
	if p1 == p2:
		print(0)
	else:
		result = abs(p1 - p2)
		for (left, right) in pepper:
			val = abs(p1 - p2 - 2 * (left - right))
			if val < result:
				result = val
		print(result)


for _ in range(int(input())):
	n = int(input())
	l1 = []
	l2 = []
	for i in range(n):
		s = input()
		a = s[:n // 2].count('1')
		b = s[n // 2:].count('1')
		if a > b:
			l1.append(a - b)
		elif a < b:
			l2.append(b - a)
	p = sum(l1)
	q = sum(l2)
	if p == q:
		print(0)
	elif p > q:
		diff = p - q
		flag = 0
		for i in range(diff // 2, 0, -1):
			a = diff - i
			if i in l1 or a in l1:
				print(abs(a - i))
				flag = 1
				break
		if flag == 0:
			print(diff)
	else:
		diff = q - p
		flag = 0
		for i in range(diff // 2, 0, -1):
			a = diff - i
			if i in l2 or a in l2:
				print(abs(a - i))
				flag = 1
				break
		if flag == 0:
			print(diff)


for _ in range(int(input())):
	n = int(input())
	l = []
	r = []
	for i in range(n):
		row = list(map(int, input()))
		l.append(sum(row[:n // 2]))
		r.append(sum(row[n // 2:]))
	res = abs(sum(l) - sum(r))
	for i in range(n):
		tl = l.copy()
		tr = r.copy()
		(tl[i], tr[i]) = (tr[i], tl[i])
		if abs(sum(tl) - sum(tr)) < res:
			res = abs(sum(tl) - sum(tr))
	print(res)


t = int(input())
while t:
	n = int(input())
	l = []
	b = []
	for i in range(0, n):
		o = input()
		l.append(o)
	(f1, s1) = (0, 0)
	for i in range(0, n):
		(f, s) = (0, 0)
		for j in range(0, n):
			if j < n // 2:
				if l[i][j] == '1':
					f += 1
					f1 += 1
			elif l[i][j] == '1':
				s += 1
				s1 += 1
		b.append([f, s])
	ans1 = abs(f1 - s1)
	a1 = f1
	b1 = s1
	for j in range(0, len(b)):
		f1 -= b[j][0]
		s1 -= b[j][1]
		f1 += b[j][1]
		s1 += b[j][0]
		ans1 = min(ans1, abs(f1 - s1))
		f1 = a1
		s1 = b1
	print(ans1)
	t -= 1


t = int(input())
while t:
	cp = 0
	pc = 0
	p1 = []
	p2 = []
	n = int(input().rstrip())
	if n % 2 == 0:
		for _ in range(n):
			st = input()
			for i in range(n // 2):
				if st[i] == '1':
					cp += 1
			p1.append(cp)
			for i in range(n // 2, n):
				if st[i] == '1':
					pc += 1
			p2.append(pc)
			cp = 0
			pc = 0
		diff = abs(sum(p1) - sum(p2))
		if diff == 0:
			print(0)
		else:
			for i in range(n):
				tp1 = sum(p1)
				tp2 = sum(p2)
				tp1 += p2[i] - p1[i]
				tp2 += p1[i] - p2[i]
				cdiff = abs(tp1 - tp2)
				if cdiff < diff:
					diff = cdiff
			print(diff)
	t -= 1


import sys
t = int(input())
while t:
	n = int(input())
	h = [[0, 0] for i in range(n)]
	p = [0, 0]
	for i in range(n):
		line = input()
		for j in range(n):
			h[i][int(2 * j / n)] += int(line[j])
			p[int(2 * j / n)] += int(line[j])
	minDiff = abs(p[0] - p[1])
	for i in range(n):
		diff = abs(p[0] - p[1] + 2 * (h[i][1] - h[i][0]))
		if diff < minDiff:
			minDiff = diff
	sys.stdout.write(str(minDiff) + '\n')
	t -= 1


try:
	for _ in range(int(input())):
		n = int(input())
		a = []
		for i in range(n):
			s = input().strip()
			a.append(s[:n // 2].count('1') - s[n // 2:].count('1'))
		diff = sum(a)
		if diff == 0:
			print(diff)
		else:
			l = [abs(diff - 2 * i) for i in a]
			print(min(l))
except:
	pass


t = int(input())
for _ in range(t):
	n = int(input())
	p1 = 0
	p2 = 0
	row1 = list()
	row2 = list()
	for __ in range(n):
		s = input()
		row1.append(sum(list(map(int, s[0:n // 2]))))
		row2.append(sum(list(map(int, s[n // 2:]))))
	p1 = sum(row1)
	p2 = sum(row2)
	diff = abs(p1 - p2)
	if diff == 0:
		print(0)
	else:
		for __ in range(n):
			diff = min(diff, abs(p1 - row1[__] + row2[__] - p2 + row2[__] - row1[__]))
		print(diff)


for T in range(int(input())):
	N = int(input())
	P = list(range(N))
	Q = [0 for x in range(N)]
	for I in range(N):
		P[I] = input()
	for I in range(N):
		for J in range(N):
			if P[I][J] == '1':
				if J < N / 2:
					Q[I] += 1
				else:
					Q[I] -= 1
	S = sum(Q)
	Z = abs(S)
	for I in range(N):
		Z = min(Z, abs(S - 2 * Q[I]))
	print(Z)


for _ in range(int(input())):
	n = int(input())
	a = []
	b = []
	q = []
	c1 = 0
	c2 = 0
	for i in range(n):
		x = [int(n) for n in input().strip()]
		a.append(x[0:n // 2].count(1))
		c1 += a[i]
		b.append(x[n // 2:n].count(1))
		c2 += b[i]
	for i in range(n):
		x = c1
		y = c2
		if x == y:
			q.append(0)
			break
		x = x - a[i] + b[i]
		y = y - b[i] + a[i]
		q.append(abs(x - y))
	print(min(q))


def findAnswer(li):
	n = len(li)
	count1 = [0] * n
	count2 = [0] * n
	for i in range(n):
		for k in range(n):
			if k < n // 2 and li[i][k] == '1':
				count1[i] += 1
			if k >= n // 2 and li[i][k] == '1':
				count2[i] += 1
	leftsum = sum(count1)
	rightsum = sum(count2)
	ans = abs(leftsum - rightsum)
	for j in range(n):
		ansfaltu = leftsum - count1[j] + count2[j] - (rightsum - count2[j] + count1[j])
		ans = min(ans, abs(ansfaltu))
	print(ans)
t = int(input())
for _ in range(t):
	n = int(input())
	li = []
	count1 = 0
	count2 = 0
	for _ in range(n):
		st = input()
		lo = list(st)
		li.append(lo)
	findAnswer(li)


t = int(input())
while t:
	t -= 1
	n = int(input())
	(ls, rs) = (0, 0)
	(mls, mrs) = ([0] * n, [0] * n)
	for i in range(n):
		x = input()
		for j in x[:n // 2]:
			mls[i] += int(j)
		for j in x[n // 2:]:
			mrs[i] += int(j)
		ls += mls[i]
		rs += mrs[i]
	res = abs(ls - rs)
	for i in range(n):
		res = min(res, abs(ls - 2 * mls[i] + 2 * mrs[i] - rs))
	print(res)


import math
for i in range(int(input())):
	n = int(input())
	left_tot = 0
	right_tot = 0
	curr = []
	for k in range(n):
		st = input()
		le = st[:n // 2].count('1')
		ri = st[n // 2:].count('1')
		left_tot += le
		right_tot += ri
		curr.append([le, ri])
	curr_tot = int(math.fabs(left_tot - right_tot))
	for h in range(len(curr)):
		new_left = left_tot
		new_right = right_tot
		new_left -= curr[h][0]
		new_left += curr[h][1]
		new_right -= curr[h][1]
		new_right += curr[h][0]
		if math.fabs(new_left - new_right) < curr_tot:
			curr_tot = math.fabs(new_left - new_right)
	print(int(curr_tot))


t = int(input())
for i in range(t):
	n = int(input())
	p1 = []
	p2 = []
	d = []
	for j in range(n):
		p = input()
		p1.append(p[:n // 2].count('1'))
		p2.append(p[n // 2:].count('1'))
		d.append(p1[j] - p2[j])
	m = abs(sum(p1) - sum(p2))
	for k in range(len(d)):
		r = abs(sum(p1) + 2 * p2[k] - sum(p2) - 2 * p1[k])
		if r < m:
			m = r
	print(m)


for _ in range(int(input())):
	N = int(input())
	differences = []
	for i in range(N):
		row = input()
		left = row[:N // 2].count('1')
		right = row[N // 2:].count('1')
		differences.append(left - right)
	s = sum(differences)
	if s == 0:
		ans = 0
	else:
		ans = min((abs(s - 2 * x) for x in differences))
	print(ans)


def answer():
	(x, y) = (0, 0)
	for i in range(n):
		for j in range(n):
			if a[i][j] == '0':
				continue
			if j < n // 2:
				x += 1
			else:
				y += 1
	ans = abs(x - y)
	for i in range(n):
		(c1, c2) = (0, 0)
		for j in range(n):
			if a[i][j] == '0':
				continue
			if j < n // 2:
				c1 += 1
			else:
				c2 += 1
		ans = min(ans, abs(x - c1 + c2 - (y - c2 + c1)))
	return ans
for T in range(int(input())):
	n = int(input())
	a = [input() for i in range(n)]
	print(answer())


t = int(input())
for _ in range(t):
	n = int(input())
	pepd = [0 for i in range(n)]
	for j in range(n):
		r = str(input())
		p1 = r[:n // 2].count('1')
		p2 = r[n // 2:].count('1')
		pepd[j] = p1 - p2
	if sum(pepd) == 0:
		print(0)
	else:
		f = sum(pepd)
		minf = abs(f)
		for d in pepd:
			newf = abs(f - 2 * d)
			if newf < minf:
				minf = newf
		print(minf)


for ii in range(int(input())):
	n = int(input())
	l = []
	(s, ss) = (0, 0)
	for i in range(n):
		sr = input()
		(p, q) = (sr[:n // 2].count('1'), sr[n // 2:].count('1'))
		l.append([p, q])
		s += p
		ss += q
	if s == ss:
		print('0')
	else:
		m = abs(s - ss)
		for i in l:
			k = abs(s - i[0] + i[1] - (ss - i[1] + i[0]))
			if k < m:
				m = k
		print(m)


for _ in range(int(input())):
	n = int(input())
	left = 0
	right = 0
	Dict = {}
	for i in range(n):
		s = input()
		curr_left = s[0:n // 2].count('1')
		curr_right = s[n // 2:n].count('1')
		left += curr_left
		right += curr_right
		Dict[i] = curr_left - curr_right
	ans = abs(left - right)
	org_ans = left - right
	for i in range(n):
		ans = min(ans, abs(org_ans - 2 * Dict[i]))
	print(ans)


for T in range(int(input())):
	N = int(input())
	P = []
	Q = [0 for x in range(N)]
	for I in range(N):
		P.append(input())
	for I in range(N):
		for J in range(N // 2):
			if P[I][J] == '1':
				Q[I] += 1
			if P[I][J + N // 2] == '1':
				Q[I] -= 1
	S = sum(Q)
	Z = {abs(S)}
	for I in range(N):
		if Q[I] != 0:
			Z.add(abs(S - 2 * Q[I]))
	print(min(Z))


for x in range(int(input())):
	n = int(input())
	l = []
	l1 = []
	l2 = []
	(p, q, p1, q1) = (0, 0, 0, 0)
	for x in range(n):
		l.append(input())
	for x in range(n):
		(p, q) = (0, 0)
		for y in range(n // 2):
			if l[x][y] == '1':
				if l[x][n - y - 1] != '1':
					p += 1
			elif l[x][n - y - 1] == '1':
				q += 1
		p1 += p
		q1 += q
		if p - q != 0:
			l1.append([p, q])
	if p1 == q1:
		print('0')
	else:
		k = p1
		k1 = q1
		for x in range(len(l1)):
			t = p1 + l1[x][1] - l1[x][0]
			t1 = q1 + l1[x][0] - l1[x][1]
			if abs(t - t1) < abs(k - k1):
				k = t
				k1 = t1
		p1 = k
		q1 = k1
		print(abs(p1 - q1))


import numpy as np
T = int(input())
for t in range(T):
	N = int(input())
	rowDiffs = []
	for n in range(N):
		s = input()
		half1 = s[:N // 2]
		half2 = s[N // 2:]
		rowDiffs.append(half2.count('1') - half1.count('1'))
	Diff = sum(rowDiffs)
	absArr = [abs(i) for i in Diff - 2 * np.array(rowDiffs)]
	ind = np.argmin(absArr)
	ans = min(min(absArr), abs(Diff))
	print(ans)


t = int(input())
while t:
	t = t - 1
	n = int(input())
	a = []
	for i in range(n):
		s = str(input())
		x = s[:n // 2].count('1') - s[n // 2:].count('1')
		a.append(x)
	y = sum(a)
	if y == 0:
		print(0)
	else:
		b = [abs(y - 2 * a[i]) for i in range(n)]
		print(min(b))


for i in range(0, int(input())):
	d = []
	t = int(input())
	for j in range(0, t):
		a = input()
		a = list(a)
		num = 0
		diff = 0
		for k in a:
			if num < t / 2:
				if k == '1':
					diff = diff + 1
			elif k == '1':
				diff = diff - 1
			num = num + 1
		d.append(diff)
	p = sum(d)
	if p == 0:
		print(0)
	else:
		min = abs(p)
		for k in range(0, len(d)):
			f = d.pop(k)
			d.insert(k, -1 * f)
			if abs(sum(d)) < min:
				min = abs(sum(d))
			d.pop(k)
			d.insert(k, f)
		print(min)


def solution():
	N = int(input())
	grid = []
	total_left = 0
	total_right = 0
	for i in range(N):
		line = [int(x) for x in list(input())]
		half = int(N / 2)
		left_sum = sum(line[:half])
		right_sum = sum(line[half:])
		total_right += right_sum
		total_left += left_sum
		grid.append([left_sum, right_sum])
	diff = abs(total_right - total_left)
	for i in range(N):
		(left_sum, right_sum) = grid[i]
		total_left += right_sum - left_sum
		total_right += left_sum - right_sum
		diff = min(diff, abs(total_right - total_left))
		total_left += left_sum - right_sum
		total_right += right_sum - left_sum
	print(diff)
T = int(input())
while T > 0:
	T = T - 1
	solution()


def peperoni(a, n):
	p1 = p2 = 0
	for i in range(n):
		for j in range(0, n // 2, 1):
			if a[i][j] == 1:
				p1 += 1
		for k in range(n // 2, n, 1):
			if a[i][k] == 1:
				p2 += 1
	return p2 - p1
testCase = int(input())
for _ in range(testCase):
	n = int(input())
	a = []
	for i in range(n):
		a += [[int(x) for x in list(input())]]
	m = peperoni(a, n)
	ans = abs(m)
	for i in range(n):
		if ans == 0:
			break
		x = a[i][0:n // 2].count(1)
		y = a[i][n // 2:n].count(1)
		t = abs(m + (2 * x - 2 * y))
		if t < ans:
			ans = t
	print(ans)


t = int(input())
for r in range(t):
	n = int(input())
	x = 0
	y = 0
	l = []
	for j in range(n):
		a = list(map(int, input()))
		l.append(a)
		for i in range(n // 2):
			x += a[i]
		for i in range(n // 2, n):
			y += a[i]
	p = abs(x - y)
	for j in range(n):
		u = 0
		v = 0
		for i in range(n // 2):
			u += l[j][i]
		for i in range(n // 2, n):
			v += l[j][i]
		if p > abs(x - y + 2 * v - 2 * u):
			p = abs(x - y + 2 * v - 2 * u)
	print(p)


for _ in range(int(input())):
	n = int(input())
	(l, s) = ([], 0)
	for i in range(n):
		s1 = input()
		a = s1[:n // 2].count('1') - s1[n // 2:].count('1')
		l.append(a)
		s += a
	if s == 0:
		print(0)
	else:
		m = 1001
		for i in l:
			m = min(m, abs(s - 2 * i))
		print(m)


t = int(input())
for i in range(t):
	n = int(input())
	arr1 = []
	arr2 = []
	for i in range(n):
		pizza = input()
		part1 = pizza[:n // 2]
		part2 = pizza[n // 2:]
		arr1.append(part1.count('1'))
		arr2.append(part2.count('1'))
	initial = abs(sum(arr1) - sum(arr2))
	x = sum(arr1)
	y = sum(arr2)
	final = [initial]
	for i in range(len(arr1)):
		x1 = x
		y1 = y
		x1 = x1 - arr1[i] + arr2[i]
		y1 = y1 - arr2[i] + arr1[i]
		final.append(abs(x1 - y1))
	print(min(final))


for T in range(int(input())):
	N = int(input())
	P = list(range(N))
	Q = [0 for x in range(N)]
	R = [0 for x in range(N)]
	for I in range(N):
		P[I] = input()
	for I in range(N):
		for J in range(N // 2):
			if P[I][J] == '1':
				Q[I] += 1
			if P[I][J + N // 2] == '1':
				R[I] += 1
	LS = sum(Q)
	RS = sum(R)
	Z = [abs(LS - RS)]
	for I in range(N):
		Z.append(abs(LS - Q[I] + R[I] - (RS - R[I] + Q[I])))
	print(min(Z))