Opgave

Je krijgt een figuur zoals hieronder: van links naar rechts gezien gaat het zwart op en neer. Het doel is een figuur te bekomen die (ook weer van links naar rechts gezien) niet meer daalt, dus enkel stijgt of gelijk blijft. Gevraagd: wat is het minimaal aantal vakjes dat zwart gekleurd moet worden om dat te bekomen?



Deze figuur laat zien - met de grijze vakjes - dat 6 vakjes volstaan: meer is niet nodig.

Invoer

De eerste regel bevat het aantal testgevallen. Elk testgeval bestaat uit een aantal regels. De eerste regel van elk testgeval bevat twee natuurlijke getallen k en r van elkaar gescheiden door één enkele spatie. Daarna volgen r regels, elk bestaande uit precies k karakters. . of * . Deze r regels geven een symbolische voorstelling van de figuur, van boven naar onder en van links naar rechts. Een wit vakje wordt aangegeven door een ., een zwart vakje door een *. Het derde (en laatste voorbeeld in de voorbeeldinvoer) komt overeen met de figuur die hiervoor werd gegeven.

Voorbeeldinvoer:

3
2 2
. *
* *
2 2
* .
* *
8 7
. . . . . . . .
. . . . . . * .
. . . . * . * *
. * . . * . * *
. * * . * * * *
. * * * * * * *
* * * * * * * * 

Uitvoer

De uitvoer bestaat uit één regel per testgeval. Elke regel bestaat uit twee gehele getallen, van elkaar gescheiden door één enkele spatie. Het eerste getal is de index van het testgeval (startend bij 1) en het tweede getal is het minimum aantal blokjes dat moet worden ingekleurd zodat de figuur enkel stijgt of gelijk blijft.

Voorbeelduitvoer:

1 0
2 1
3 6