Problem

When she is bored, Mija sometimes likes to play a game with matrices. She tries to transform one matrix into another with the fewest moves. For Mija, one move is swapping any two rows of the matrix or any two columns of the matrix.

Today, Mija has a very special matrix M. M is a 2N by 2N matrix where every entry is either a 0 or a 1. Mija decides to try and transform M into a checkerboard matrix where the entries alternate between 0 and 1 along each row and column. Can you help Mija find the minimum number of moves to transform M into a checkerboard matrix?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing a single integer: N. The next 2N lines each contain 2N characters which are the rows of M; each character is a 0 or 1.

Output

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the minimum number of row swaps and column swaps required to turn M into a checkerboard matrix. If it is impossible to turn M into a checkerboard matrix, y should be "IMPOSSIBLE".

Limits

Memory limit: 1 GB.

1 ≤ T ≤ 100.

Small dataset (4 Points)

Time limit: 60 10 seconds.

1 ≤ N ≤ 10.

Large dataset (9 Points)

Time limit: 120 20 seconds.

1 ≤ N ≤ 10³.

Sample

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

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

In the first sample case, M is already a checkerboard matrix.

In the second sample case, Mija can turn M into a checkerboard matrix by swapping columns 1 and 2 and then swapping rows 1 and 2.

In the third sample case, Mija can never turn M into a checkerboard matrix; it doesn't have enough 1s.