You are given a binary matrix $A$ of size $n \times n$. Rows are numbered from top to bottom from $1$ to $n$, columns are numbered from left to right from $1$ to $n$. The element located at the intersection of row $i$ and column $j$ is called $A_{ij}$. Consider a set of $4$ operations:

Cyclically shift all rows up. The row with index $i$ will be written in place of the row $i-1$ ($2 \le i \le n$), the row with index $1$ will be written in place of the row $n$.

Cyclically shift all rows down. The row with index $i$ will be written in place of the row $i+1$ ($1 \le i \le n - 1$), the row with index $n$ will be written in place of the row $1$.

Cyclically shift all columns to the left. The column with index $j$ will be written in place of the column $j-1$ ($2 \le j \le n$), the column with index $1$ will be written in place of the column $n$.

Cyclically shift all columns to the right. The column with index $j$ will be written in place of the column $j+1$ ($1 \le j \le n - 1$), the column with index $n$ will be written in place of the column $1$.

The $3 \times 3$ matrix is shown on the left before the $3$-rd operation is applied to it, on the right — after.

You can perform an arbitrary (possibly zero) number of operations on the matrix; the operations can be performed in any order.

After that, you can perform an arbitrary (possibly zero) number of new xor-operations:

Select any element $A_{ij}$ and assign it with new value $A_{ij} \oplus 1$. In other words, the value of $(A_{ij} + 1) mod 2$ will have to be written into element $A_{ij}$.

Each application of this xor-operation costs one burl. Note that the $4$ shift operations — are free. These $4$ operations can only be performed before xor-operations are performed.

Output the minimum number of burles you would have to pay to make the $A$ matrix unitary. A unitary matrix is a matrix with ones on the main diagonal and the rest of its elements are zeros (that is, $A_{ij} = 1$ if $i = j$ and $A_{ij} = 0$ otherwise).


-----Input-----

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) —the number of test cases in the test.

The descriptions of the test cases follow. Before each test case, an empty line is written in the input.

The first line of each test case contains a single number $n$ ($1 \le n \le 2000$)

This is followed by $n$ lines, each containing exactly $n$ characters and consisting only of zeros and ones. These lines describe the values in the elements of the matrix.

It is guaranteed that the sum of $n^2$ values over all test cases does not exceed $4 \cdot 10^6$.


-----Output-----

For each test case, output the minimum number of burles you would have to pay to make the $A$ matrix unitary. In other words, print the minimum number of xor-operations it will take after applying cyclic shifts to the matrix for the $A$ matrix to become unitary.


-----Examples-----

Input
4
3
010
011
100
5
00010
00001
10000
01000
00100
2
10
10
4
1111
1011
1111
1111
Output
1
0
2
11


-----Note-----

In the first test case, you can do the following: first, shift all the rows down cyclically, then the main diagonal of the matrix will contain only "1". Then it will be necessary to apply xor-operation to the only "1" that is not on the main diagonal.

In the second test case, you can make a unitary matrix by applying the operation $2$ — cyclic shift of rows upward twice to the matrix.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Complete search

Implementation

Constructive algorithms
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
def count(b, n):
	l = []
	for i in range(n):
		c = 0
		for j in range(n):
			if b[j][j - i] == '1':
				c += 1
		l.append(c)
	return l
for i in range(int(input())):
	s = input()
	n = int(input())
	p = []
	for j in range(n):
		p.append(input())
	s = count(p, n)
	print(n - 2 * max(s) + sum(s))


T = int(input())
q = []
for i in range(T):
	input()
	n = int(input())
	m = []
	for i in range(n):
		c = input()
		m.append(c)
	q.append((n, m))

def solve(n, mat):
	max_long = 0
	id = -1
	counter = []
	for r in range(n):
		tot = 0
		for j in range(n):
			c = (r + j) % n
			if mat[j][c] == '1':
				tot += 1
		if tot > max_long:
			max_long = tot
			id = i
		counter.append(tot)
	counter.remove(max_long)
	print(n - max_long + sum(counter))
for (n, mat) in q:
	solve(n, mat)


from math import *
from collections import *
import math, os, sys, heapq, bisect, random
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for case in range(how_much_noob_I_am):
		inp()
		n = inpu()
		l = [inp() for i in range(n)]
		res = 0
		cnt2 = 0
		for i in range(n):
			cnt2 += l[i].count('1')
		for i in range(n):
			cnt = 0
			p = i
			for j in range(n):
				if l[j][p % n] == '1':
					cnt += 1
				p += 1
			res = max(res, cnt)
		print(n + cnt2 - 2 * res)
main()


def solve():
	ans = 0
	for s in range(n):
		i = 0
		j = s
		diag = 0
		while i < n:
			if matrix[i][j] == '1':
				diag += 1
			i += 1
			j += 1
			if j == n:
				j = 0
		ans = max(ans, diag)
	return ans
for _ in range(int(input())):
	a = input()
	n = int(input())
	matrix = []
	ones = 0
	for _ in range(n):
		matrix.append(input())
		ones += matrix[-1].count('1')
	print(ones - 2 * solve() + n)


for _ in range(int(input())):
	thousandminusseven = input()
	n = int(input())
	a = [input() for _ in range(n)]
	for i in range(1, n):
		a[i] = a[i][i:n] + a[i][:i]
	cnt = sum((sum((c == '1' for c in t)) for t in a))
	bans = n ** 2
	mxc = max((sum((a[i][j] == '1' for i in range(n))) for j in range(n)))
	print(cnt + n - 2 * mxc)


for _ in range(int(input())):
	input()
	n = int(input())
	o = 0
	arr = list()
	for i in range(n):
		s = input()
		arr.append(s)
		o += s.count('1')
	best = 0
	for i in range(n):
		curr = 0
		for j in range(n):
			if arr[j][(j + i) % n] == '1':
				curr += 1
		best = max(best, curr)
	print(o - best + (n - best))


import sys

def main():
	input = sys.stdin
	if len(sys.argv) >= 2:
		input = open(sys.argv[1], 'r')
	n = int(input.readline().strip())
	for i in range(n):
		input.readline()
		size = int(input.readline().strip())
		mtrx = [[int(t) for t in input.readline().strip()] for i in range(size)]
		countOnesOnDiag = lambda idx, m, sz: sum([m[(idx + k) % size][k] for k in range(sz)])
		OnesOnDiag = [countOnesOnDiag(i, mtrx, size) for i in range(size)]
		tmax = max(OnesOnDiag)
		tsum = sum(OnesOnDiag)
		print(size - tmax + tsum - tmax)
main()


t = int(input())
while t:
	n = input()
	if n != '':
		n = int(n)
		ones = [0] * n
		for turn in range(n):
			s = input()
			for i in range(n):
				if s[i] == '1':
					ones[i - turn] = ones[i - turn] + 1
		print(sum(ones) - max(ones) + n - max(ones))
	else:
		continue
	t = t - 1


def intlist():
	return [int(i) for i in input()]

def solve():
	pp = input()
	n = int(input())
	l = []
	oness = 0
	for i in range(n):
		ll = intlist()
		oness += ll.count(1)
		l.append(ll + ll)
	ma = 0
	for i in range(0, n):
		d = 0
		for j in range(0, n):
			d += l[j][i + j]
		if d > ma:
			ma = d
	ans = oness - ma + (n - ma)
	return ans
t = input()
for tt in range(int(t)):
	print(solve())


for _ in range(int(input())):
	input()
	n = int(input())
	a = [list(map(int, input())) for _ in range(n)]
	s = sum(map(sum, a))
	u = max((sum((a[i][(i + d) % n] for i in range(n))) for d in range(n)))
	print(n - u + (s - u))


for i in range(int(input())):
	input()
	(ans, size) = (0, int(input()))
	matrix = [list(map(int, list(input()))) for line in range(size)]
	diagonals = []
	for x in range(size):
		diagonals.append(sum((matrix[y][(x + y) % size] for y in range(size))))
	best = sorted(diagonals)[-1]
	print(str(size - best + sum(diagonals) - best))


for _ in range(int(input())):
	input()
	n = int(input())
	x = 0
	mat = []
	ans = 0
	for i in range(n):
		temp = input()
		mat.append(temp)
		x += temp.count('1')
	for i in range(n):
		cur = 0
		for j in range(n):
			if mat[j][(j + i) % n] == '1':
				cur += 1
		ans = max(ans, cur)
	print(x - ans + (n - ans))


def solution():
	newline = input()
	n = int(input())
	A = []
	count_one = 0
	for _ in range(n):
		row = [int(i) for i in input()]
		A.append(row)
		count_one += sum(row)
	max_one = 0
	for i in range(n):
		record = 0
		for j in range(n):
			record += A[j][(i + j) % n]
		max_one = max(max_one, record)
	zero_to_one = n - max_one
	one_to_zero = count_one - max_one
	print(zero_to_one + one_to_zero)
t = int(input())
for _ in range(t):
	solution()


def solve():
	input()
	n = int(input())
	matrix = tuple((tuple((int(i) for i in iter(input()))) for _ in range(n)))
	cached = tuple((sum((matrix[k][k + i - n] for k in range(n))) for i in range(n)))
	print(sum(cached) + n - 2 * max(cached))
for _ in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	input()
	n = int(input())
	sum_per_diagonal = [0] * n
	for i in range(n):
		digits = input()
		for (j, digit) in enumerate(digits):
			sum_per_diagonal[(n + j - i) % n] += digit == '1'
	print(sum(sum_per_diagonal) + n - 2 * max(sum_per_diagonal))


T = int(input())
while T > 0:
	T -= 1
	input()
	n = int(input())
	arr = []
	for i in range(n):
		tmp = input()
		arr.append(tmp)
	ans = 0
	cnt = 0
	for i in range(n):
		tmp = 0
		for j in range(n):
			if arr[j][(i + j) % n] == '1':
				tmp += 1
				cnt += 1
		ans = max(ans, tmp)
	print(cnt + n - ans - ans)


def minburles(matrix):
	n = len(matrix)
	num1 = 0
	numd = 0
	for j0 in range(n):
		j = j0
		cnt = 0
		for i in range(n):
			if matrix[i][j] == 1:
				cnt += 1
				num1 += 1
			j += 1
			j %= n
		numd = max(numd, cnt)
	return n + num1 - 2 * numd
t = int(input())
for _ in range(t):
	_ = input()
	n = int(input())
	matrix = []
	for i in range(n):
		matrix.append([int(x) for x in input()])
	print(minburles(matrix))