Shoot the Turrets (Small)

The fight to free the city from the alien invaders is over. The city is a grid with $R$ rows and $C$ columns. Some cells are buildings and the rest are streets. Nobody can see through a building, shoot through it, or walk through it. Everybody can see, shoot and walk through a street.

The defeated invaders left automatic security turrets in the city. Every turret stands on a street, never inside a building. Soldiers are on the streets too. At the start no soldier shares a cell with a turret.

The turrets do not move. They are small, so they block neither sight nor shots. A soldier cannot walk into a cell that holds a live turret, but can walk over that cell once the turret is destroyed. A turret sees a soldier only in the cells it has a horizontal or vertical line of sight to. When a soldier enters such a cell, the turret holds its fire. When the soldier tries to leave such a cell, whether she walked in or started there, the turret fires. The turret does not count shooting as movement, so the soldier can still fire from that cell. No soldier ever dies: in the worst case she waits, motionless, for help.

Each soldier makes at most $M$ unit moves, and each move goes to a horizontally or vertically adjacent cell. Soldiers walk through each other and block no line of sight. Each soldier carries one bullet. A soldier who has a turret in her horizontal or vertical line of sight can shoot it and destroy it. One shot destroys one turret. The soldiers shoot so well that a bullet passes over any turret or soldier in the line of sight and hits a turret farther away.

You are given the map with the soldier and turret positions marked. What is the largest number of turrets the soldiers can destroy?

The first line holds the number of test cases $T$. The first line of each test case holds the width of the map $C$, the height of the map $R$, and the number of unit moves each soldier can make $M$. The next $R$ lines hold $C$ characters each, where . is a street, # is a building, S is a soldier and T is a turret.

Limits

• $1 \le T \le 100$
• $0 \le M < C \times R$
• $1 \le C \le 30$
• $1 \le R \le 30$
• The number of S characters is between 1 and 10.
• The number of T characters is between 1 and 10.

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 largest number of turrets that can be destroyed.

For the explanations below, number the soldiers from 1 and the turrets from 1. The numbering reads left to right along the top row, then left to right along the next row down, and so on, and the soldier numbers are independent of the turret numbers.

In the second case soldier 3 moves up three cells and destroys turret 3. Soldier 1 then moves up one cell and right one cell, onto the square turret 3 held, and shoots past turret 2 to destroy turret 1. Soldier 2 moves up three cells and destroys turret 2, so all three turrets fall.

In the third case soldier 1 moves up one cell and right three cells and destroys turret 2. Soldier 2 moves up one cell and right three cells and destroys turret 1. Soldier 6 moves down one cell and right three cells and destroys turret 3. The other soldiers do not have enough moves to reach any turret.

In the fourth case the soldier cannot reach a cell in the turret's row or column, so the turret survives.