Tô màu 2D

Time limit: 1.0s , Memory limit: 256M , Points: 0 (partial)

Cho một bảng vuông kích thước $N \times N$ ~N \times N~, các hàng được đánh số từ $1$ ~1~ đến $N$ ~N~ từ trên xuống dưới và các cột được đánh số từ $1$ ~1~ đến $M$ ~M~ từ trái sang phải. Mỗi ô $(i,j)$ ~(i,j)~ nằm ở tại hàng $i$ ~i~, cột $j$ ~j~ của bảng có thể được tô bởi một trong hai màu trắng hoặc đen và sẽ mang màu mới nhất được tô.

Ban đầu, mọi ô của bảng đều được tô màu trắng. Bạn có thể thực hiện thao tác tô màu như sau bằng cách chọn một ô $(x,y)$ ~(x,y)~:

Tô màu cho các ô nằm trên đoạn nối hai ô $(x,y)-(x,x)$ ~(x,y)-(x,x)~ và đoạn nối hai ô $(x,y)-(y,y)$ ~(x,y)-(y,y)~.
Việc tô màu cho các ô được thực hiện bằng cách tô màu trái ngược với màu hiện tại của ô đó $($ ~(~ô màu trắng được tô màu đen và ngược lại $)$ ~)~

Lưu ý rằng việc thực hiện như trên được tính là một lần thao tác.

Ví dụ, hình sau minh họa thao tác tô màu với các ô được chọn theo thứ tự: $(1,4)$ ~(1,4)~, $(3,5)$ ~(3,5)~, $(5,1)$ ~(5,1)~, $(3,3)$ ~(3,3)~:

Yêu cầu: Cho một bảng vuông với mỗi ô được tô màu trắng hoặc đen. Nhiệm vụ của bạn hãy xác định số lần thao tác ít nhất để thu được bảng vuông đó. Có thể nhận thấy rằng với mọi bảng vuông, luôn luôn tồn tại ít nhất một chuỗi các thao tác phù hợp.

Input

Dòng đầu tiên chứa số nguyên $N$ ~N~ $(1 \le N \le 4000)$ ~(1 \le N \le 4000)~.
Bảng vuông được mô tả trong $N$ ~N~ tiếp theo, mỗi dòng chứa một chuỗi độ dài $N$ ~N~ chỉ chứa kí tự 0 tương ứng màu trắng hoặc ký tự 1 tương ứng màu đen.