P16745 [GKS 2019 #H] Diagonal Puzzle

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$ 是使所有方格变黑所需的最少步数。

### 限制条件 $1 \le T \le 100$。 保证存在一种方法能使所有方格变黑。 **测试集 1（可见）** $2 \le N \le 8$。 **测试集 2（隐藏）** $2 \le N \le 100$。 翻译由 DeepSeek V4 Pro 完成