你生活在一个二维平面上，你最喜欢去的地方之一是镜子大厅。镜子大厅是一个网格状的房间（当然是二维的）。网格中的每个方格要么包含一面方形镜子，要么是空地，要么是你自己。你的宽度和高度均为 0，且你位于所在网格方格的中心。

尽管你非常小，但当光线精确地反射回你时，你就能看到自己的倒影。例如，考虑以下布局，其中 '#' 表示完全填满该方格的方形镜子，'.' 表示空地，大写字母 'X' 表示你位于该方格的中心：

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

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

不幸的是，镜子大厅里雾气很大，所以你无法看到超过 $D$ 个单位距离以外的东西。假设 $D=3$。如果你向上看，你的倒影将在 1 个单位距离处（0.5 到镜子，0.5 返回）。如果你向右看，你的倒影将在 3 个单位距离处（1.5 到镜子，1.5 返回），你将能够看到它。如果你向下看，你的倒影将在 5 个单位距离处，你将无法看到它。

理解光在镜子大厅中如何传播非常重要。光沿直线传播，直到碰到镜子。如果光碰到镜子的任何部分（角除外），它将以正常方式反射：它将以等于入射角的反射角弹回。另一方面，如果光接触到镜子的角，情况就比较复杂了。以下图示解释了各种情况：

在以下情况中，光接近一个角并被反射，改变了它的方向：

在前两种情况下，光在两面相邻镜子的交点处接近它们。光的反射方式与它击中长镜子中间时的反射方式相同。在第三种情况下，光接近三面相邻镜子的角，并沿原路返回。

在以下情况中，光接近一面或多面镜子的角，但没有反弹，而是继续沿相同方向传播：

这种情况发生在光到达距离镜子角 0 的位置，但不需要穿过镜子就能继续沿相同方向传播时。通过这种方式，一束光可以穿过两面斜向相邻的镜子之间——实际上是穿过一个大小为 0 的空间。好在它的大小也是 0，所以它能穿过去！

在最后一种情况下，光接近一面镜子的角并被销毁：

镜子挡在了光的路径上，且光束没有接近任何其他镜子的角。

注意，光在碰到你时会停止，但它必须击中你所在网格方格的精确中心。

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

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含三个空格分隔的整数 $H$、$W$ 和 $D$。接下来的 $H$ 行，每行包含 $W$ 个字符。这些字符构成了如上所述的镜子大厅地图。

输出格式

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

数据范围

内存限制：1GB。 时间限制：10 秒。 $1 \le T \le 100$。 $3 \le H, W \le 30$。 $1 \le D \le 50$。 地图中的所有字符均为 '#'、'.' 或 'X'。 每个地图中恰好有一个字符为 'X'。 每个地图的第一行、最后一行、第一列和最后一列完全由 '#' 字符填充。

子任务 1

'#' 字符的数量不超过 $2W+2H-4$。

子任务 2

没有额外的限制。

样例

样例输入 1

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.#
#.#..#
#...##
######

样例输出 1

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

说明

在第一个用例中，如果你直视上、下、左或右，光传播的距离正好为 1。

在第二个用例中，如果你向右上、左上、右下或左下看，光传播的距离为 1.414...。由于光不会穿过你，直视上方只能看到一个自己的倒影。

在第五个用例中，虽然附近的镜子足够近，可以将光反射回你，但击中镜子角的光被销毁了，而不是被反射。