뒤죽박죽 행

0과 1 값을 갖는 N x N 행렬이 주어진다. 행렬에서 서로 인접한 임의의 두 행을 맞바꿀 수 있다.

목표는 행렬의 모든 1 값이 주대각선 위가 아닌 주대각선상이나 그 아래에 있도록 하는 것이다. 즉, 1 ≤ X ≤ N인 각 X에 대해, X행에서 X열보다 오른쪽에 1 값이 없어야 한다.

목표를 달성하는 데 필요한 행 교환의 최소 횟수를 구한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 60

소형 데이터 세트

1 ≤ N ≤ 8

대형 데이터 세트

1 ≤ N ≤ 40

입력의 첫 번째 줄에는 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 정수 N 하나가 주어진다. 이어지는 N개의 각 줄에는 N개의 문자가 들어 있다. 각 문자는 0 또는 1이다.

각 테스트 케이스마다 다음을 출력한다.

Case #X: K

여기서 X는 1부터 시작하는 테스트 케이스 번호이고, K는 행렬의 모든 1 값이 주대각선상이나 그 아래에 있도록 하는 데 필요한 행 교환의 최소 횟수이다.

각 테스트 케이스에 해답이 존재함이 보장된다.