Farmer John thỉnh thoảng gặp rắc rối với những thiếu niên buồn chán đến trang trại vào ban đêm và xô ngã bò của ông. Một buổi sáng, ông tỉnh dậy và phát hiện chuyện đó lại xảy ra: \(N^2\) con bò của ông bắt đầu buổi tối bằng việc gặm cỏ theo một lưới vuông \(N \times N\) hoàn hảo (\(1 \leq N \leq 10\)), nhưng giờ đây một số con đã bị xô ngã.

May thay, Farmer John đã dùng các bộ phận từ máy kéo và xe nâng để chế tạo một cỗ máy tuyệt diệu mang tên Cow-Untipperator 3000, có thể lật cả nhóm bò lớn cùng lúc, giúp ông dựng tất cả bò đứng dậy nhanh nhất có thể. Ông có thể dùng máy lên bất kỳ "hình chữ nhật góc trên bên trái" nào trong lưới bò, tức là một lưới con hình chữ nhật chứa con bò ở góc trên bên trái. Khi đó, máy lật mọi con bò trong hình chữ nhật này, dựng những con đang ngã đứng dậy, nhưng không may cũng làm những con vốn đang đứng bị ngã! Nói cách khác, máy "đảo" trạng thái của từng con bò trong hình chữ nhật.

Farmer John nhận thấy rằng bằng cách sử dụng máy đủ nhiều lần trên một tập hợp hình chữ nhật thích hợp, cuối cùng ông có thể đưa tất cả bò trở lại trạng thái đứng đúng đắn. Hãy giúp ông xác định số lần sử dụng máy ít nhất cần thiết để làm điều đó.

Lưu ý rằng dùng máy hai lần trên cùng một hình chữ nhật là vô ích vì trạng thái của đàn bò trong hình chữ nhật đó rốt cuộc không thay đổi. Vì vậy, bạn chỉ cần xét việc dùng máy trên mỗi hình chữ nhật góc trên bên trái nhiều nhất một lần.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\).

Mỗi dòng trong \(N\) dòng tiếp theo chứa một xâu gồm \(N\) ký tự; mỗi ký tự là 0 (biểu thị một con bò đang đứng) hoặc 1 (biểu thị một con bò bị ngã).

Dữ liệu ra

In số lần ít nhất Farmer John cần sử dụng Cow-Untipperator 3000 để dựng tất cả bò đứng dậy.

Ví dụ

3
001
111
111

2

110
000
000

Nguồn

USACO 2017 January Contest, Bronze — Cow Tipping. Tác giả đề: Nathan Pinsker.

https://usaco.org/index.php?page=viewproblem2&cpid=689