체커보드 행렬

Mija는 심심할 때 가끔 행렬을 이용한 게임을 즐긴다. Mija는 최소 횟수의 이동으로 한 행렬을 다른 행렬로 변환하려 한다. Mija에게 한 번의 이동은 행렬의 임의의 두 행을 서로 바꾸거나 임의의 두 열을 서로 바꾸는 것이다.

오늘 Mija에게는 매우 특별한 행렬 M이 있다. M은 모든 원소가 0 또는 1인 2N × 2N 행렬이다. Mija는 M을 각 행과 열을 따라 원소가 0와 1 사이에서 번갈아 나타나는 체커보드 행렬로 변환하려 한다. Mija가 M을 체커보드 행렬로 변환하는 데 필요한 최소 이동 횟수를 구하도록 도와주자.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100.

작은 데이터 세트

시간 제한: 60초. 1 ≤ N ≤ 10.

큰 데이터 세트

시간 제한: 120초. 1 ≤ N ≤ $10^{3}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 하나의 정수 N이 포함된 줄로 시작한다. 다음 2N개의 줄에는 각각 M의 행을 나타내는 2N개의 문자가 주어지며, 각 문자는 0 또는 1이다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 M을 체커보드 행렬로 만드는 데 필요한 행 교환과 열 교환의 최소 횟수이다. M을 체커보드 행렬로 만드는 것이 불가능하다면 y는 "IMPOSSIBLE"이어야 한다.

첫 번째 예제 케이스에서 M은 이미 체커보드 행렬이다.

두 번째 예제 케이스에서 Mija는 열 1와 2를 서로 바꾼 다음 행 1와 2를 서로 바꾸어 M을 체커보드 행렬로 만들 수 있다.

세 번째 예제 케이스에서 Mija는 M을 절대로 체커보드 행렬로 만들 수 없다. 1의 개수가 충분하지 않다.