All Submissions


There's been a Flood in a town neighboring of your's as a result of heavy rainfall this year and water have filled everywhere. You have been selected for purchasing and installing pumps that will pump out the water. These is no limit on the amount of water a pump can draw, but they must be placed correctly so that all the water flows into a pump, with no lakes or puddles left over. The pumps are really expensive and your job is to determine the minimum number of pumps that are needed to be bought.

You have been given a rectangular grid representing height of each square meter of this town. It contains only lowercase English characters with 'a' meaning lower ground and 'z' meaning higher ground. Water flows from a cell to every other cell which shares an edge and is of equal or lower height. The town is surrounded by high mountains on all sides so you can assume that water cannot flow off the map.You must print the minimum number of pumps that can be placed to ensure that all rain will eventually flow to some pump.

Input
First Line contains T denoting Number of test cases.
Every Test case begins with 2 Integers R,C denoting the number of rows and columns respectively.
Then R lines follow each containing C characters.

Output
T lines each containing an integer representing the minimum number of pumps required.

Constraints
T <= 111
1<=R,C<=100
Every character of map is between 'a' - 'z'.

Sample Input
2
5 5
ccccc
cbbbc
cbabc
cbbbc
ccccc
2 2
ab
ba


Sample Output
1
2


Problem Setter : Arjun Singh Bhatia
Problem Tester : Shikhar Sharad


Languages: Brain,C,C++,Java,Pascal,Perl,PHP,Python,Ruby,Text

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0