#1592 Flood Relief

48  5 s   128 MB

Description

Global warming has caused your home town to receive far more rain than usual, and it is in danger of becoming flooded. You have been put in charge of buying and installing pumps that will carry away the water. There is no limit on how much water a pump can handle, but they must be placed correctly so that all the water will flow into a pump, with no lakes or even puddles left over. The pumps are also expensive, so you must determine the minimum number that need to be bought.
You are given a height map. This is a rectangular grid representing the height of each square meter of your town. It contains only lowercase letters ('a' - 'z'), with 'a' meaning low ground and 'z' meaning high ground. Water flows from a cell to every cell that shares an edge and is of equal or lower height. The town is surrounded by high mountains on all sides, so water cannot flow off the map. You must find out the minimum number of pumps that can be placed to ensure that all rain will eventually flow to some pump.

Input

The first line of the input gives a number of test cases, T.
The first line of each case gives the number of rows R (1 <= R <= 50) and columns of the map C (1 <= C <= 50).
Next R line gives the map each containing C lowercase alphabet characters of the corresponding row of the map.

Output

For each test case, output the minimum number of pumps on each line.

Sample Output

2
5 5
ccccc
cbbbc
cbabc
cbbbc
ccccc
2 2
ab
ba
1
2