题目描述

Kibur 为你设计了一个新谜题！谜题包含一个 $N \times N$ 的方格网格。每个方格是黑色或白色。目标是用尽可能少的步数使所有方格变为黑色。

在一步操作中，你可以选择任意一条对角线，并翻转该对角线上所有方格的颜色（黑色变白色，白色变黑色）。例如，下面展示了 $3 \times 3$ 网格中所有 $10$ 条可能的对角线。

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

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

给定棋盘的初始配置，求使所有方格变黑所需的最少步数。保证存在一种方法能使所有方格变黑。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$，表示网格的大小。随后 $N$ 行，每行包含 $N$ 个字符，描述棋盘的初始配置。如果第 $r$ 行第 $c$ 列的方格初始为白色，则该位置字符为 .（ASCII 码 46）；否则为 #（ASCII 码 35），表示黑色。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是使所有方格变黑所需的最少步数。

3
3
..#
#.#
#..
5
.####
#.###
##.##
###.#
#####
2
##
##

Case #1: 3
Case #2: 2
Case #3: 0

提示

限制条件

$1 \le T \le 100$。

保证存在一种方法能使所有方格变黑。

测试集 1（可见）

$2 \le N \le 8$。

测试集 2（隐藏）

$2 \le N \le 100$。

翻译由 DeepSeek V4 Pro 完成