teddy online judge

46. Space

Limite de tiempo : 1 seg.   Total runs : 19  Aceptados : 6

This is the return of the space cowboy
Inter-planetary good vibe zone
At the speed of Cheeba we'll go deeper
Maybe I'll have to get high just to get by.
— Jamiroquai, The Return of the Space Cowboy

Samus Aran es una cazarrecompensas espacial, universalmente reconocida por su increíble agilidad y su arsenal de armas disponibles. Durante una de sus misiones, sin embargo, su traje espacial se averió, y quedó totalmente incapacitada para saltar, además de tener un uso limitado del resto de su arsenal. Samus decide que está dispuesta a hacer lo que sea para sobrevivir, y para ello necesita tu ayuda.

Samus te ha enviado un pequeño mapa con las ubicaciones de pequeñas plataformas donde se puede parar sin peligro alguno, y que además cuentan con la propiedad de que son enganchables mediante el Grappling Beam de Samus, permitiéndole subir. Sin embargo, la pila de su traje es muy limitada, y sólo puede activar el Grappling Beam un número limitado de veces.

En su estado incapacitado, Samus únicamente puede moverse 1 bloque horizontalmente si es que se encuentra parada actualmente encima de una plataforma, caer 1 bloque verticalmente o en diagonal hacia abajo si no está encima de una plataforma, y usar el Grappling Beam para agarrarse de una plataforma que esté justo encima de ella. Una vez enganchada una plataforma con el rayo, Samus puede subir y bajar libremente en una línea vertical (sin atravesar ninguna plataforma) y dejarse caer de nuevo. Samus morirá si no le es posible llegar a la salida del mundo, o si se cae por debajo del mapa que te envió.

Input

La primer línea de la entrada contiene un único número, N, el número de casos de prueba que siguen. Cada caso de prueba consiste de una línea con 3 números separados por espacios, R, C y G (1 ≤ R, C, G ≤ 100). R siendo el número de renglones del mapa, C el número de columnas y G el número de veces que puede utilizar el Grappling Beam. Después, vienen R líneas con C caracteres, que representan el mapa. Una x representa una plataforma sólida, una S el punto inicial donde se encuentra Samus, un . espacio libre y una O la salida hacia su nave espacial. Se garantiza que en cada caso existirá exactamente una S y una O.

Output

Para cada caso, debes imprimir una línea "Caso c: Samus sobrevive usando g veces el rayo.", si es posible que Samus llegue a la salida, siendo c el número secuencial del caso y g el número mínimo de veces que debe usar el rayo para sobrevivir. En caso de que no sobreviva, debes imprimir "Caso c: Samus muere.".

Sample Input/Output