Descripción

Washington, un perrito gerente de un centro comercial, está muy preocupado porque se aproxima el Black Friday y sabe lo que significa.

El centro comercial puede representarse como una cuadrícula de \(N\) filas por \(M\) columnas. Cada celda puede estar vacía, contener un obstáculo, un cliente o una tienda.

Un cliente puede moverse hacia arriba, abajo, izquierda o derecha, siempre que la celda destino no sea un obstáculo y se encuentre dentro de los límites de la cuadrícula.

Washington conoce muy bien a su clientela pues cada cliente intentará llegar a la tienda más cercana, pero solo lo hará si la distancia del camino más corto es de a lo más \(K\) pasos. Si el camino más corto supera \(K\) pasos, o no existe, el cliente pierde el interés y se marcha.

Ahora Washington quiere saber cuántos clientes pueden llegar a alguna tienda en a lo más \(K\) pasos.

Entrada

La primera línea contiene tres enteros \(N\) \((1 \leq N \leq 1000)\), \(M\) \((1 \leq M \leq 1000)\) y \(K\) \((1 \leq K \leq 1000)\), el número de filas, el número de columnas y el límite máximo de pasos que un cliente está dispuesto a recorrer respectivamente.

Las siguientes \(N\) líneas contienen una cadena de exactamente \(M\) caracteres. Cada carácter representa una celda y puede ser

• '.' una celda vacía.
• '#' un obstáculo.
• 'C' un cliente.
• 'T' una tienda.

Salida

Muestra el número de clientes que pueden llegar a alguna tienda en a lo más \(K\) pasos.

Ejemplo

Entrada

2 3 6
.C#
T.C

Salida

2

Entrada

4 4 2
###C
C.#.
..#.
#TTT

Salida

0

Entrada

1 7 3
T..C..T

Salida

1

Entrada

5 1 1000
.
.
.
.
.

Salida

0

Entrada

5 5 25
C#TTT
#TTTT
TTTTT
TTTTT
TTTTT

Salida

0