Một hệ thống chiếu sáng thông minh trong tòa nhà được mô phỏng bằng lưới vuông ~N \times N~. Ở mỗi ô có một bóng đèn, trạng thái bật là 1, tắt là 0.
Sau khi lắp đặt, khách hàng yêu cầu biến lưới đèn ban đầu A thành lưới đèn đích B theo các quy tắc:

• Mỗi đèn trên lưới chỉ được tác động nhiều nhất một lần.
• Khi tác động vào một đèn, trạng thái của chính nó sẽ đổi (bật↔tắt).
• Đồng thời, bốn đèn kề cạnh (chung cạnh với đèn được tác động) cũng đổi trạng thái nếu tồn tại.

Yêu cầu

Xác định có thể biến đổi từ lưới ban đầu A sang lưới đích B hay không.
Nếu không thể, in -1. Nếu có thể, in số lần tác động ít nhất để đạt được lưới B.

Dữ liệu

• Dòng 1: số nguyên dương ~N~ (~1 \le N \le 16~).
• ~N~ dòng tiếp theo: mỗi dòng gồm ~N~ số 0/1 mô tả lưới A (1 là bật, 0 là tắt).
• ~N~ dòng cuối: mỗi dòng gồm ~N~ số 0/1 mô tả lưới B.

Các số có thể phân tách bởi dấu cách hoặc liền nhau (ví dụ 1011).

Kết quả

Ghi ra một số nguyên duy nhất — số lần tác động ít nhất để biến A thành B. Nếu không thể biến đổi, in -1.

Ví dụ

Input

3
1 0 1
0 1 0
1 0 1
1 1 1
1 0 1
1 1 1

Output

1

Gợi ý/Thảo luận (Có thể đúng hoặc sai)

• Đây là biến thể của bài Lights Out: mỗi thao tác tương đương cộng vector bật/tắt theo mô-đun 2 cho ô được bấm và các ô kề cạnh của nó.
• Có thể giải bằng:
  1) Thử toàn bộ ~2^N~ cấu hình tác động ở hàng đầu, rồi suy ra các hàng tiếp theo ~(O(N^3 / 64)~ với bitset).
  2) Hoặc hệ phương trình tuyến tính trên GF(2) với ~N^2~ biến, dùng Gaussian elimination bitset.

Chấm điểm

• Subtask 1 — 30%: ~N \le 4~.
• Subtask 2 — 30%: ~N \le 8~.
• Subtask 3 — 40%: Không có ràng buộc bổ sung ngoài đề.