Cho bảng ~N \times N~ ~(N \leq 14)~. Mỗi ô là ~1~ số ~0~ hoặc ~1~. Một phép ~Touch(i, j)~ cho phép đổi ngược giá trị của ô ~(i, j)~ ~-~ hàng ~i~, cột ~j -~ và các ô kề cạnh (nếu có) từ ~0~ thành ~1~ và từ ~1~ thành ~0~. Trạng thái đích là trạng thái mà cả bảng đều là ~0~ hoặc đều là ~1~.

Yêu cầu: Tìm số bước ít nhất để đến được trạng thái đích. Nếu ko có cách nào in ra ~- 1~.

Input

• Dòng đầu tiên chứa số ~N~ ~(1 \leq N \leq 14)~.
• ~N~ dòng tiếp theo, mỗi dòng chứa ~N~ kí tự '0' hoặc '1' mô tả trạng thái của bảng.

Output

• ~1~ số duy nhất là số bước ít nhất để đến được trạng thái đích. Nếu ko có cách nào in ra ~- 1~.

Giới hạn

Có ~40\%~ số test có ~N \leq 4~

Sample Input

3
110
001
100

Sample Output

4

Note

~4~ phép touch cần dùng ở vị trí ~(1, 1), (1, 2), (1, 3), (2, 1)~.