뒤엉킨 행 (라지)

0과 1로만 이루어진 $N \times N$ 행렬이 주어진다. 인접한 두 행은 서로 교환할 수 있다.

목표는 행렬의 모든 1을 주대각선 위 또는 주대각선 아래에 놓는 것이다. 즉 $1 \le X \le N$을 만족하는 모든 $X$에 대해, $X$번째 행에는 $X$번째 열보다 오른쪽에 1이 하나도 없어야 한다.

목표를 이루는 데 필요한 행 교환의 최소 횟수를 구한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 정수 $N$이 하나 주어진다. 이어지는 $N$개의 줄에는 각각 $N$개의 문자가 있고, 각 문자는 0 또는 1이다.

제한

• $1 \le T \le 60$
• $1 \le N \le 40$

각 테스트 케이스마다 다음 형식으로 한 줄을 출력한다.

Case #X: K

$X$는 1부터 시작하는 테스트 케이스 번호이고, $K$는 모든 1을 주대각선 위 또는 주대각선 아래에 놓는 데 필요한 행 교환의 최소 횟수이다.

모든 테스트 케이스에 해가 존재함이 보장된다.