뒤죽박죽 행 (작은 입력)

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 8$

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

Case #X: K

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

모든 테스트 케이스에는 해가 존재한다.