대각선 퍼즐

키부르가 여러분이 풀 새로운 퍼즐을 만들었다. 이 퍼즐은 $N \times N$ 격자로 이루어져 있다. 각 칸은 검은색 또는 흰색이다. 퍼즐의 목표는 가능한 한 적은 횟수의 이동으로 모든 칸을 검은색으로 만드는 것이다.

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

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


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

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

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 격자의 크기 $N$이 적힌 줄로 시작한다. 그다음 $N$개의 줄에 각각 $N$개의 문자가 주어지며, 격자의 초기 상태를 나타낸다. $r$행 $c$열의 문자가 .이면 그 칸은 처음에 흰색이고, #이면 검은색이다.

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

$1 \le T \le 100$.

모든 칸을 검은색으로 만드는 것이 가능하다고 보장된다.

첫 번째 예제에서 필요한 최소 이동 횟수는 3이다. 과정은 다음과 같다.

..#    ..#    .##    ###
#.# -> ..# -> #.# -> ###
#..    ##.    ##.    ###

두 번째 예제에서 필요한 최소 이동 횟수는 2이다. 과정은 다음과 같다.

.####    #####    #####
#.###    #####    #####
##.## -> ##### -> #####
###.#    #####    #####
#####    ####.    #####

세 번째 예제는 모든 칸이 이미 검은색이므로 답은 0이다.