a180285 has been lucky enough to be chosen as an exchange student to the Meow Planet. In reality, this is a special mission to investigate whether the Meow people have any plans to invade Earth. The Meow people are indeed planning to invade! After receiving this critical information from a180285, the Earth Defense Team has decided to formulate a counter-invasion plan.

A vital path for the Meow people to reach Earth can be viewed as an $n \times m$ grid. The Meow people will start from position $S$ on the map and head towards the Earth's entrance $T$. To resist the Meow invasion, the Earth Defense Team plans to place some turrets (at most $K$ of them) on the grid. A turret can attack the 8 surrounding cells (the 8 directions are: East, South, West, North, Northeast, Northwest, Southeast, Southwest) (as shown in the figure below, a turret in the middle cell can attack the eight surrounding cells). In addition, the Earth Defense Team can also place an unlimited number of obstacles on the map, making it impossible for the Meow people to pass through cells with obstacles.

The figure on the right is an example of a $3 \times 3$ map, where $X$ represents a turret and $\#$ represents an obstacle. The Meow people cannot pass through cells with turrets or obstacles. In this map, the damage received by the Meow people as they walk from $S$ to $T$ is as follows: at $S(1,0)$ the damage received is 2 (turrets at $(0,0)$ and $(2,1)$ can hit $S$), at the empty space $(1,1)$ the damage received is 3 (simultaneously hit by turrets at $(0,0)$, $(0,2)$, and $(2,1)$), and at $T(1,2)$ the damage received is 2 (turrets at $(0,2)$ and $(2,1)$ can hit $T$). Thus, the total damage received is $2+3+2=7$.

As a member of the Earth Defense Team, please arrange the layout for the Meow people such that the damage they receive is maximized. Note that if there are multiple paths from $S$ to $T$, the Meow people will choose the one with the minimum damage.

Input

The first line contains three integers $n, m, K$, representing the length and width of the map, and the maximum number of turrets that can be placed. The next $n$ lines each contain $m$ characters, where '#' represents an existing obstacle on the map, and '.' represents an empty space. It is guaranteed that a path from $S$ to $T$ exists on the original map.

Output

Output the maximum damage the Meow people will receive after you have arranged the layout optimally and they have chosen their best strategy. Note that you must ensure that after the layout is finished, the Meow people can still reach the destination $T$ from the starting point $S$ via one or more paths, otherwise they will organize a large-scale invasion.

Examples

Input 1

3 3 1
S.T
...
...

Output 1

7

Note

One optimal layout for the example is as follows:

S#T
.X.
...

Constraints

For 30% of the data, it is guaranteed that: $1 \le N, M \le 6$

For 100% of the data, it is guaranteed that: $1 \le N \le 6$, $1 \le M \le 20$, $1 \le K \le 15$, and a path from $S$ to $T$ is guaranteed to exist.