체커보드 행렬 (큰 입력)

미자는 심심할 때 행렬을 가지고 논다. 한 행렬을 다른 행렬로 바꾸되 이동 횟수를 최소로 줄이려고 한다. 미자에게 이동 한 번은 행렬의 두 행을 서로 바꾸거나 두 열을 서로 바꾸는 것이다.

오늘 미자에게는 아주 특별한 행렬 $M$이 있다. $M$은 모든 원소가 0 또는 1인 $2N \times 2N$ 행렬이다. 미자는 $M$을 체커보드 행렬로 바꾸려고 한다. 체커보드 행렬은 각 행과 각 열을 따라 0과 1이 번갈아 나오는 행렬이다. $M$을 체커보드 행렬로 만드는 최소 이동 횟수를 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 정수 $N$이 주어진다. 다음 $2N$개의 줄에는 각각 $2N$개의 문자가 주어지고, 이것이 $M$의 각 행이다. 각 문자는 0 또는 1이다.

제한

• $1 \le T \le 100$
• $1 \le N \le 10^3$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 $M$을 체커보드 행렬로 만드는 데 필요한 행 교환과 열 교환 횟수의 최솟값이다. $M$을 체커보드 행렬로 만들 수 없으면 $y$ 자리에 IMPOSSIBLE을 출력한다.

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

두 번째 예제 케이스에서는 1열과 2열을 바꾼 다음 1행과 2행을 바꾸면 체커보드 행렬이 된다.

세 번째 예제 케이스에서는 1의 개수가 모자라서 어떤 방법으로도 체커보드 행렬을 만들 수 없다.