|
ACM - Universidad Autonoma de Puebla |
Chencha tiene que entregar un kilo de tortillas a una señora muy rara que vive en un cuartito construido en el rincón de un terreno rectangular ubicado en la esquina de una de las manzanas de Pueblo Chico. Chencha entra al terreno por la esquina de la manzana (es decir, por la esquina del terreno opuesta al rincón donde está construido el cuartito) y caminaría en línea recta de no ser por los nopales de espinas afiladas que cultiva la señora en su terreno. Por eso únicamente caminaparalelamente a las calles y siempre lo hace acercándose al cuartito, paso a paso. Escribe un programa que cuente el número de maneras en que Chencha puede dar sus pasos para llegar al cuartito sin que tropiece con ningún nopal.
La entrada consiste de varios casos de prueba. En la primera línea se encuentra exclusivamente el número N de casos de prueba (1≤N≤100). La primera línea de cada caso contiene dos enteros positivos n y m (n + m ≤ 30) que representan las dimensiones del terreno rectangular medidas en pasos de Chencha. Las siguientes n líneas contienen una representación de la configuración de nopales en el terreno. Un símbolo * significa que Chencha puede pisar en ese lugar, y un símbolo # significa que en ese lugar se encuentra un nopal. El primer símbolo de la primera línea será siempre una E, indicando el lugar por donde Chencha entra al terreno. El m-ésimo símbolo de la n-ésima línea será siempre un +, indicando que en ese lugar se encuentra el cuartito de la señora.
Para cada caso de prueba, imprime una línea con alguno de los siguientes formatos:
Ejemplo de entrada |
Ejemplo de salida |
|---|---|
2 |
Chencha puede caminar de 2 maneras |