题目描述

给定一个大小为 $n×n$ 的二进制矩阵 $A$ 。行从上到下从 $1$ 到 $n$ 编号，列从左到右从 $1$ 到 $n$ 编号。位于第 $i$ 行和第 $j$ 列交点处的元素称为 $A_{ij}$ 。考虑一个由 $4$ 个操作组成的集合：

将所有行循环向上移动。行索引为 $i$ 的行将被写入行 $i-1$ 的位置 $(2≤i≤n)$ ，行索引为 $1$ 的行将被写入行 $n$ 的位置。
将所有行循环向下移动。行索引为 $i$ 的行将被写入行 $i+1$ 的位置 $(1≤i≤n-1)$ ，行索引为 $n$ 的行将被写入行 $1$ 的位置。
将所有列循环向左移动。列索引为 $j$ 的列将被写入列 $j-1$ 的位置 $(2≤j≤n)$ ，列索引为 $1$ 的列将被写入列 $n$ 的位置。
将所有列循环向右移动。列索引为 $j$ 的列将被写入列 $j+1$ 的位置 $(1≤j≤n-1)$ ，列索引为 $n$ 的列将被写入列 $1$ 的位置。

左侧显示的是在进行第三种操作之前的 $3×3$ 矩阵，在右侧则是经过操作后的结果。

你可以在矩阵上可以执行任意（可能为零）数量的操作；操作可以以任意顺序执行。

之后，您可以执行任意（可能为零）数量的新异或操作：

选择任意元素 $A_{ij}$ ，并将其赋予新值 $A_{ij} ⊕ 1$ 。换句话说，将 $(A_{ij} + 1) \% 2$ 的值写入元素 $A_{ij}$ 。

每个异或操作的代价为 1。请注意， $4$ 个移位操作是免费的。这 $4$ 个操作只能在执行异或操作之前进行。

输出您需要支付的最少费用，以使矩阵 $A$ 成为单位矩阵。单位矩阵是指主对角线上元素为 1，其余元素为 0 的矩阵（即，如果 $i=j$ ，则 $A_{ij}=1$ ，否则 $A_{ij}=0$ ）。

输入格式

输入的第一行包含一个整数 $t(1≤t≤10^4)$ ——测试用例的数量。

接下来是每个测试用例的描述。在每个测试用例之前，输入中都有一个空行。

每个测试用例的第一行包含一个数字 $n(1≤n≤2000)$ 。

接下来的 $n$ 行，每行包含恰好 $n$ 个字符，仅由零和一组成。这些行描述了矩阵元素的值。

保证在所有测试用例中， $n^2$ 的总和不超过 $4×10^6$ 。

对于每个测试用例，输出最小的操作代价，使得矩阵A变成单位矩阵。换句话说，输出在应用循环移位操作后，将A矩阵变成单位矩阵所需的最小异或操作次数。

在第一个测试用例中，你可以按照以下方式操作：首先，将所有行循环向下移动，然后矩阵的主对角线将只包含 1。然后需要对不在主对角线上的唯一的 1 应用异或操作。

在第二个测试用例中，你可以通过将操作 $2$ （将行循环向上移动两次）应用到矩阵中来制作一个单位矩阵。