Description

你生活在一个二维平面上，你最喜欢去的地方之一是镜厅。镜厅是一个房间（当然是二维的），以网格的形式铺设。网格上的每个格子要么放置着一个方形镜子，要么是空地，要么是你自己。你自身的宽度和高度都为 $0$，且你位于你所在格子的正中心。

尽管你很小，但只要反射光线正好返回到你这里，你就能看到自己的倒影。例如，考虑如下布局，其中 # 表示完全填满格子的方形镜子，. 表示空地，大写字母 X 表示你处于该格子的中心：

######
#..X.#
#.#..#
#...##
######

如果你直视正上方或正右方，你都能看到自己的倒影。

不幸的是，镜厅里雾很大，所以你看不超过 $D$ 单位的距离。假设 $D=3$。如果你向上看，你的倒影距离你 1 单位远（0.5 到镜子，0.5 再回来）。如果你向右看，你的倒影距离你 3 单位远（1.5 到镜子，1.5 再回来），你能看到它。如果你向下看，你的倒影距离你 5 单位远，你就看不到了。

理解光线在镜厅中的传播方式非常重要。光线会沿直线传播，直到遇到镜子。如果光线击中了镜子的某一部分（不是角落），它会以正常方式反射：反射角等于入射角。如果光线正好打在镜子的角上，情况会更复杂。下图解释了各种情况：

在下面这些情况下，光线到达了一个角落，并被反射，方向发生了变化：

前两种情况中，光线以与长镜中点相同的方式，被两块相邻镜子交汇处反射。第三种情况中，光线到达了三块相邻镜子的角落，正好沿原路返回。

在下面这些情况下，光线到达了一个或多个镜子的角落，但不会反弹，而是继续保持原方向前进：

这种情况发生在光线到达镜子角落的距离为 $0$，但要继续保持原方向前进时并不需要穿过镜子。这样，光线就可以穿过对角相邻的两块镜子之间的“零宽度”空隙——好在光线自身也没有宽度，所以它能穿过去！

在最后一种情况下，光线到达了一块镜子的角落并被“消灭”：

此时镜子正好挡在光路上，且光线没有同时到达其他镜子的角落。

注意：光线遇到你时会停止，但必须正好击中你所在格子的中心。

你能看到多少个自己的倒影？

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为三个用空格分隔的整数 $H$、$W$ 和 $D$。接下来 $H$ 行，每行 $W$ 个字符，表示该组测试的镜厅地图，含义如上所述。

Output Format

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为你能看到的自己倒影的数量。

6
3 3 1
###
#X#
###
3 3 2
###
#X#
###
4 3 8
###
#X#
#.#
###
7 7 4
#######
#.....#
#.....#
#..X..#
#....##
#.....#
#######
5 6 3
######
#..X.#
#.#..#
#...##
######
5 6 10
######
#..X.#
#.#..#
#...##
######

Case #1: 4
Case #2: 8
Case #3: 68
Case #4: 0
Case #5: 2
Case #6: 28

Hint

样例说明

在第 1 个样例中，如果你直视正上、下、左、右，光线恰好传播距离为 1。

在第 2 个样例中，如果你沿对角线（右上、左上、右下、左下）方向看，光线传播距离为 $1.414\dots$。由于光线不会穿过你自己，直视正上方只能看到一个自己的倒影。

在第 5 个样例中，虽然附近的镜子足够近可以反射光线回来，但如果光线正好打在镜子的角落，它会被消灭而不是反射。

限制条件

• $1 \leq T \leq 100$
• $3 \leq H, W \leq 30$
• $1 \leq D \leq 50$
• 每个地图中的字符均为 #、. 或 x
• 每个地图中恰好有一个 x
• 每个地图的第一行、最后一行、第一列和最后一列全部为 #

测试集 1（15 分，可见结果）

• # 的总数不超过 $2W + 2H - 4$

测试集 2（25 分，隐藏结果）

• 小数据集的限制不适用

翻译由 ChatGPT-4.1 完成。