Start: Oct, 02, 2021 08:00:00
专题3 广搜及优化
End: Oct, 23, 2021 12:00:00
Time elapsed:
Time remaining:

【NOIP模拟赛181006】水流 1225

Time Limit:  1 Sec    Memory Limit:   128 MB
Submission:7     AC:4     Score:100


Description

全球气候变暖,小镇A面临水灾。于是你必须买一些泵把水抽走。泵的抽水能力可以认为是无穷大,但你必须把泵放在合适的位置,从而能使所有的水能流到泵里。小镇可以认为是N * M的矩阵。矩阵里的每个单元格都是一个‘a’- ‘z’小写字母,该小写字母表示该格子的高度,字母大的表示该单元格比较高,反之,表示该格子高度比较低。当前单元格的水可以流到上、下、左、右四个格子,但必须满足这些格子的高度是小于或者等于当前格子的高度。现在,给你一些N * M的矩阵,你至少要买多少个泵,才能把所有格子的水都能被抽走?

Input

多组测试数据。

第一行:K,表示有K组测试数据。(1<=K<=5)

接下来有K组测试数据,每组测试数据格式如下:

第一行:两个正数, N,M。1<=N,M<=50,表示小镇的大小。

接下来有N行,每行有M个小写字母,表示小镇的地图。

Output

共K行,每行对应一组数据。至少要买多少个泵,才能把所有格子的水都能抽走。

Samples

input:
2 5 5 ccccc cbbbc cbabc cbbbc ccccc 4 9 cbabcbabc cbabcbabc cbabcbabc cbabcbabc
output:
1 2