Snakes and transition from Capitalism to Socialism

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
After a long duration of the painful, torturous and tumultuous periods of capitalism in Snakeland, now the snakes have decided to adopt socialism. The houses in Snakeland are arranged in a rectangular fashion of dimension n * m. The wealth of the snake in the house at cell (i, j) is given by a[i][j] rupees.
A bill has been passed for making a smooth transition from capitalism to socialism. At the end of each hour, the wealth of a snake will grow and will become equal to the highest wealth that its neighbor had (at the start of the hour). That is, consider the maximum wealth among its neighbors at the start of the hour, and this snake's wealth will become equal to that at the end of the hour. Note that this increase in wealth will happen simultaneously for each snake. Two houses are said to be neighbors of each other if they share a side or corner with each other. Find out the minimum number of hours required for this transition.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space separated integers: n, m.
Each of the next n lines contains m space separated integers. The jth integer in the ith row denotes a[i][j].
Output
For each test case output a single integer corresponding to the minimum number of hours required for the transition.
Constraints
 1 ≤ T ≤ 4
 1 ≤ n, m ≤ 500
 1 ≤ a[i][j] ≤ 10^{6}
Example
Input 3 2 2 1 1 1 1 2 2 1 1 1 2 3 4 1 2 1 2 1 1 1 2 1 1 2 2 Output 0 1 2
Explanation
Example 1. The wealth of all the snakes is already equal. So, no time is required for the transition.
Example 2. At the end of the first hour, the wealth of snakes at cells (1, 1), (2,1) and (1, 2) will change from 1 to 2. Then, the wealth of all the snakes becomes equal, and hence it required a total of 1 hour.
Example 3. At the end of the first hour, the distribution of wealth of Snakeland will be as given below:
2 2 2 2 2 2 2 2 1 2 2 2
After the end of the second hour, the wealth of all the snakes will be equal. So, the answer is 2.
Author:  admin2 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/SNSOCIAL 
Tags  admin2, bfs, easymedium, graphtheory, snckpb17 
Date Added:  31052017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, SCM chicken, PYP3, CLOJ, 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. 