대각선 퍼즐

Kibur가 여러분이 풀 새로운 퍼즐을 만들었다! 이 퍼즐은 N×N 정사각형 격자로 이루어져 있다. 각 칸은 검은색 또는 흰색이다. 퍼즐의 목표는 가능한 한 적은 이동으로 모든 칸을 검은색으로 만드는 것이다.

한 번의 이동으로 임의의 칸 대각선 하나를 선택하고 그 대각선에 있는 모든 칸의 색을 뒤집을 수 있다(검은색은 흰색이 되고 흰색은 검은색이 된다). 예를 들어, 3×3 격자에서 가능한 10개의 대각선은 아래에 나와 있다.

/..      ./.      ../      ...      ...
...      /..      ./.      ../      ...
...      ...      /..      ./.      ../


...      ...      \..      .\.      ..\
...      \..      .\.      ..\      ...
\..      .\.      ..\      ...      ...

보드의 초기 배치가 주어질 때, 모든 칸을 검은색으로 만드는 데 필요한 최소 이동 횟수는 얼마인가? 모든 칸을 검은색으로 만드는 것이 가능함이 보장된다.

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 모든 칸을 검은색으로 만드는 것이 가능함이 보장된다.

테스트 세트 1 (공개)

2 ≤ N ≤ 8.

테스트 세트 2 (비공개)

2 ≤ N ≤ 100.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 격자의 크기인 정수 N을 포함하는 한 줄로 시작한다. 그다음 각각 격자의 초기 배치를 설명하는 N개의 문자를 포함하는 N개의 줄이 주어진다. r번째 줄의 c번째 문자는 r번째 행과 c번째 열에 있는 칸이 처음에 흰색이라면 문자 .(ASCII 번호 46)이다. 그렇지 않으면 검은색임을 나타내는 #(ASCII 번호 35)이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 (1부터 시작하는) 테스트 케이스 번호이고, y은 모든 칸을 검은색으로 만드는 데 필요한 최소 이동 횟수이다.

예제 케이스 #1에서 필요한 최소 이동 횟수는 아래와 같이 3이다.

예제 케이스 #2에서 필요한 최소 이동 횟수는 아래와 같이 2이다.

예제 케이스 #3에서는 격자의 모든 칸이 이미 검은색이므로 답은 0이다.