Ma trận qua gương

Bối cảnh

Cho một ma trận với \(n\) hàng và \(n\) cột. Mỗi ô chứa \(0\) hoặc \(1\).

Yêu cầu

Trong một thao tác, bạn có thể chọn một ô và đảo ngược giá trị của nó (từ \(0\rightarrow 1\) hoặc \(1\rightarrow 0\)). Tìm số phép toán tối thiểu bạn cần để có được một hình vuông mà giá trị các ô của nó không đổi khi xoay \(0°, 90°, 180°\) và \( 270°\).

Input

Dòng đầu chứa một số nguyên \(t\ (1\leq t\leq 100)\) là số lượng test.

Dòng đầu của mỗi test là một số nguyên \(n\ (1\leq n\leq 100)\) là kích thước của ma trận.

\(n\) dòng tiếp theo, mỗi dòng là \(n\) kí tự \(a_{i,j}\ (0\leq a_{ij}\leq 1)\) là giá trị mỗi ô trong ma trận.

Output

In ra \(t\) dòng, mỗi dòng chứa một số nguyên là số thao tác tối thiểu để làm cho ma trận không thay đổi khi được xoay \(0°, 90°, 180°\) và \(270°\).

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

5
3
010
110
010
1
0
5
11100
11011
01011
10011
11000
5
01000
10101
01010
00010
01001
5
11001
00000
11111
10110
01111

Output

1
0
9
7
6

Giải thích ví dụ

Ở test đầu tiên, ta có thể thực hiện các thao tác để biến ma trận thành \(\begin{matrix}0 & 1 & 0\\ 1 & 1 & 1\\ 0 & 1 & 0\end{matrix}\) . Từ đó ma trận sẽ giữ nguyên khi thực hiện các phép xoay.

Ở test thứ hai, mọi phần tử trong ma trận đều không đổi khi xoay, ta không cần thực hiện bất cứ thao tác nào.

Thông tin học tập

• Buổi: B12
• Concepts: matrices, symmetry, index transformations, counting
• Giới hạn kiến thức: B01-B12
• Time limit: 1 second
• Memory limit: 128 MB
• Point: 30