Skiing

All submissions for this problem are available.
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 testcases.
First line of each testcase 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 testcase 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 testcases ≤ 1,000
 1 ≤ sum of M in all testcases ≤ 1,000
 1 ≤ height of snow ≤ 1,000,000,000
Example
Input: 2 3 3 1 2 2 2 1 1 2 1 1 3 3 3 2 2 2 1 1 2 1 1 Output: 2 1
Explanation
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
Author:  kingofnumbers 
Tags  cook88, greedy, kingofnumbers, kingofnumbers, likecs, scc, sorting 
Date Added:  17112017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 