Labyrinth P79535

You are given an R × C grid. Some cells, marked with ‘#’, have a wall. The rest of cells are free, and they are marked with ‘.’. There are two exceptions: one free cell is marked with ‍‘S’ (it is your starting position), and another free cell is marked with ‘T’ (it has a treasure).

Your goal is to reach the treasure as fast as possible. Every second, you can either move to an adjancent free cell, or hit an adjancent wall with a hammer. You know that every wall vanishes after H hits.

Input

Input consists of several cases, each with R, C and H, followed by R lines with C characters each. Assume that R and C are between 1 and 1000, and that H is between 1 and 10⁵.

Output

For every case, print the minimum time to reach the treasure from the starting position.