Chocolate con almendras
A Marta y a Raúl les encanta el chocolate, relajarse tomando unas onzas después de cenar. Hoy en el supermercado han encontrado una muy buena oferta de chocolate con almendras. Aunque es el favorito de Marta, Raúl odia encontrarse tropezones cuando disfruta del chocolate; prefiere que este se vaya derritiendo en su boca, sin notar las almendras.
Después de pensárselo un rato, han decidido comprar unas cuantas tabletas y dividirlas para que las onzas con almendras queden separadas de las onzas sin ellas. Las tabletas solamente pueden partirse de forma cómoda en horizontal o vertical, por las separaciones ya marcadas entre onzas. Una vez que la tableta está divida en dos, cada una de las partes puede seguir siendo dividida.
Ahora se preguntan cuántos cortes tendrán que hacer como mínimo para dividir cada una de las tabletas en porciones que solamente tengan onzas con almendras u onzas sin almendras.
Entrada
La entrada está formada por una serie de descripciones de tabletas de chocolate. Cada una comienza con una línea con dos números, la cantidad de filas F y columnas C en que está dividida en onzas la tableta (ambas entre 1 y 20). A continuación aparecen F líneas, cada una con C caracteres. El carácter '.' indica una onza sin almendras y el carácter '#' indica una onza con almendras.
Salida
Para cada tableta se escribirá en una línea el mínimo número de cortes que hacen falta para separar las onzas con almendras de las que no las tienen. Por ejemplo, la siguiente figura muestra una división óptima de la tableta del primer caso de prueba, donde hacen falta 7 cortes.
Entrada de ejemplo
5 5 .##.. .#### ##... ..... ..### 1 6 ...### 2 2 #. .#
Salida de ejemplo
7 1 3