Read problems statements in Russian and Vietnamese as well.
Chef and Hasan went for skiing in a rectangular field, the field can be represented as a grid of N rows and M columns, rows are numbered from 1 to N starting from top, columns are numbered from 1 to M starting from left, each cell has a a number representing the height of the snow on this particular part of the field.

after skiing for a while in the field they decided to play a game, first hasan has to choose a set of cells S not necessarily adjacent and show this set to Chef.

after that, Chef has to choose exactly one cell d not necessarily from set S and tell it to Hasan.

finally, Hasan has to choose one cell from set S and start skiing from that cell and try to reach cell d that the chef just chose, if he couldn't then Chef wins, otherwise Hasan wins.

When Hasan is skiing, he can move from one cell to another iff both cells are adjacent (they share a side) and the height of destination cell is not more than the height of current cell.

it's obvious that it's easy for Hasan to win this game, because he can simply choose all cells to be in set S, but he want the set S to have minimum number of cells to prove that he is very skilled in skiing.

knowing that both players play optimally, please help Hasan to find minimum number of cells to be in set S to guarantee the winning for him.

------ Input ------

First line contains integer T donating the number of test-cases.
First line of each test-case contains two integers n and m donating the number of rows and columns respectively.
Each of the following n lines contains m numbers donating the heights of the field

------ Output ------

For each test-case output a single line containing a single integer donating minimum number of cells has to be in set S so that Hasan guarantee winning

------ Constraints ------

Should contain all the constraints on the input data that you may have. Format it like:

$1 ≤ T ≤ 100$
$1 ≤ N, M ≤ 1,000$
$1 ≤ sum of N in all test-cases ≤ 1,000$
$1 ≤ sum of M in all test-cases ≤ 1,000$
$1 ≤ height of snow ≤ 1,000,000,000$

----- Sample Input 1 ------
2
3 3
1 2 2
2 1 1
2 1 1
3 3
3 2 2
2 1 1
2 1 1
----- Sample Output 1 ------
2
1
----- explanation 1 ------
Example case 1. Hasan has to select at least two cells to be in S so that he guarantee he can reach all other cells starting from anyone of them, example of cells to choose (2,1) and (1,2)

Example case 2. if Hasan chose cell (1,1) to be in S then he can reach any cell starting from it and thus guarantee winning

见题面

见题面