13611361 SUSTech Online Judge
Problem 1361 --[Hard] Skylar's Magic Matrix

1361: [Hard] Skylar's Magic Matrix

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 5  Solved: 2
[Submit][Status][Web Board]


A matrix is magic, if the difference between its maxmium and mimimum elements ≤ \(m\). Skylar has a large \(N*N\) matrix \(M\). She would like to know size of the biggest magic sub-matrix of \(M\).


Input contains multiple test cases. The first line of input contains a single integer \(T (1 \leq T \leq 1000) \). The number of test cases.

For each case, the first line contains two numbers \(N (1 \leq N \leq 500) \) and \(M (0 \leq M \leq 100000) \), representing the given matrix is \(N\) square matrix and magic equilibrium value is \(M\). Each of the next \(N\) rows contains \(N\) integers, representing the large matrix. Elements are positive integers and not larger than \(10^5\). It is guaranteed that the sum of \(N^3\) for all test cases is not exceed \(2\cdot 10^8\).


For each case, print size of the biggest magic sub-matrix of \(M\) in one line.

Sample Input

2 0
3 3
2 3
3 1
2 4 3
3 4 2
4 3 2

Sample Output