Lớp Bi đang có phong trào chơi Rubic, nhưng Bi chơi rất "gà" chỉ xoay được tối đa hai mặt. Bi phát minh ra một Rubic mới như sau: Cho một ma trận vuông kích thước ~n~ chứa các số ~0, 1~ (~0~ màu đỏ, ~1~ màu đen gọi là rubic hai màu). Mục đích đặt ra là chuyển ma trận trên về ma trận toàn số ~0~ (màu đỏ).

Phương pháp chuyển bằng cách lật các phần tử của một mảng con hai chiều (gọi là hình chữ nhật, tương tự nhưng không giống xoay rubic) khi đó các phần tử thuộc mảng con sẽ ~0~ chuyển thành ~1~ và ngược lại.

Quy định hình chữ nhật phải có góc tọa độ trái trên bằng tọa độ trái trên của ma trận.

Lập trình tính giúp Bi số lần lật ít nhất để chuyển một mảng ban đầu về mảng chứa toàn nút màu đỏ.

Input

Dòng đầu tiên chứa số nguyên ~n~ thỏa ~1 \le n \le 10~.

~n~ dòng tiếp theo, mỗi dòng chứa xâu nhị phân độ dài ~n~.

Output

In ra kết quả cần tìm.

Samples

Sample Input 1

3
001
111
111

Sample Output 1

2

Note

Bi mất ~2~ lần chuyển như sau:

001     110     000
111 ->  000 ->  000
111     000     000