Khi cảm thấy buồn chán, Mija đôi khi thích chơi một trò chơi với các ma trận. Cô ấy cố gắng biến đổi một ma trận này thành một ma trận khác với số bước di chuyển ít nhất. Đối với Mija, một bước di chuyển là hoán đổi bất kỳ hai hàng nào của ma trận hoặc bất kỳ hai cột nào của ma trận.

Hôm nay, Mija có một ma trận rất đặc biệt \(M\). \(M\) là một ma trận kích thước \(2N \times 2N\), trong đó mỗi phần tử là 0 hoặc 1. Mija quyết định thử và biến đổi \(M\) thành một ma trận bàn cờ (checkerboard matrix), nơi các phần tử xen kẽ giữa 0 và 1 dọc theo mỗi hàng và mỗi cột. Bạn có thể giúp Mija tìm số bước di chuyển tối thiểu để biến đổi \(M\) thành một ma trận bàn cờ không?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo. Mỗi bộ thử nghiệm bắt đầu bằng một dòng chứa một số nguyên duy nhất: \(N\). \(2N\) dòng tiếp theo, mỗi dòng chứa \(2N\) ký tự là các hàng của \(M\); mỗi ký tự là 0 hoặc 1.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là số lần hoán đổi hàng và hoán đổi cột tối thiểu cần thiết để biến \(M\) thành một ma trận bàn cờ. Nếu không thể biến \(M\) thành ma trận bàn cờ, y sẽ là "IMPOSSIBLE".

Ràng buộc

• \(1 \le T \le 100\).

Phân nhóm

• Small dataset: \(1 \le N \le 10\).
• Large dataset: \(1 \le N \le 10^3\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
1
01
10
2
1001
0110
0110
1001
1
00
00

Case #1: 0
Case #2: 2
Case #3: IMPOSSIBLE

Nguồn

Google Code Jam 2014, Chung kết thế giới, bài Checkerboard Matrix.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.