Hall of Mirrors (Large)

Problem

You live on a 2-dimensional plane, and one of your favourite places to visit is the Hall of Mirrors. The hall is a room, a 2-dimensional one of course, laid out on a grid. Every cell of the grid holds a square mirror, empty space, or you. You have width 0 and height 0, and you stand at the exact centre of your cell.

Even at that size you see your reflection whenever light comes back to you exactly. In the map below, # is a mirror that completely fills its cell, . is empty space, and X marks the cell at whose centre you stand.

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

Looking straight up or straight to the right shows you a reflection.

The hall is foggy, so you cannot see anything further than $D$ units away. Suppose $D = 3$ . Looking up, your reflection is 1 unit away (0.5 to the mirror and 0.5 back). Looking right, it is 3 units away (1.5 there and 1.5 back), so you still see it. Looking down, it is 5 units away and you do not see it.

Light travels in a straight line until it meets a mirror. If it strikes any part of a mirror other than a corner, it bounces off with the angle of reflection equal to the angle of incidence. If it would touch the corner of a mirror, the situation splits into cases.

In these cases light reaches a corner, is reflected, and changes direction:

In the first two diagrams light reaches the point where two adjacent mirrors meet, and it is reflected exactly as if it had hit the middle of one long mirror. In the third diagram light reaches the corners of three adjacent mirrors and returns in exactly the direction it came from.

In these cases light touches the corners of one or more mirrors, does not bounce, and keeps its direction:

This happens when light reaches distance 0 from the corner of a mirror but does not have to pass through that mirror to continue in the same direction. A ray can therefore slip between two mirrors that are diagonally adjacent, through a gap of size 0. The ray has size 0 as well, so it fits.

In the last case light reaches the corner of one mirror and is destroyed:

That mirror lay in the path of the light, and the ray did not reach the corner of any other mirror.

Written out without the diagrams: let light arrive at a point where four cells meet. Let $F$ be the cell it would enter if it kept going, and let $S_1$ and $S_2$ be the two other cells that touch that point (the fourth one is the cell the light is leaving). If $F$ is empty, the light keeps its direction and enters $F$ . If $F$ is a mirror and exactly one of $S_1$ and $S_2$ is a mirror, those two mirrors form a straight wall and the light bounces off it. If $F$ , $S_1$ and $S_2$ are all mirrors, the light returns the way it came. If $F$ is a mirror and neither $S_1$ nor $S_2$ is, the light is destroyed.

Light stops when it hits you, but it has to hit the exact centre of your cell.

How many images of yourself can you see?

Input

The first line of the input holds the number of test cases $T$ . Each test case starts with a line of three space separated integers $H$ , $W$ and $D$ . The next $H$ lines hold $W$ characters each and give the map of the hall for that test case.

Limits

$1 \le T \le 100$
$3 \le H, W \le 30$
$1 \le D \le 50$
Every character of every map is #, . or X.
Exactly one character of each map is X.
The first row, the last row, the first column and the last column of each map are filled with #.

Output

For each test case, print one line in the form "Case #x: y", where x is the test case number starting from 1 and y is the number of reflections of yourself that you can see.

Notes

In case 1 of the first example, light travels exactly distance 1 whether you look up, down, left or right.

In case 2 of the first example, light travels distance 1.414... if you look up-right, up-left, down-right or down-left. Light does not travel through you, so looking straight up shows one image only.

In case 5 of the first example, the mirror beside you is close enough to send light back to you, but light that reaches the corner of that mirror is destroyed instead of being reflected.

In the second example, looking up and to the left sends light between the corners of two diagonally adjacent mirrors. The light then reaches the corner of the room, returns along the same path and hits you after $3\sqrt{2} \approx 4.243$ units, so that image is visible when $D = 5$ and not when $D = 4$ .