You are given a grid consisting of n rows each of which is dived into m columns. The rows are numbered from 1 to n from top to bottom, and the columns are numbered from 1 to m from left to right. Each cell is identified by a pair (x, y), which means that the cell is located in the row x and column y.
Your goal is to delete a row x (1 < x < n) and a column y (1 < y < m), after this the matrix will be divided into 4 parts. Let us define the beauty of each part as the maximum value inside it. Your task is to choose x and y such that the difference between the largest and smallest beauties is as minimal as possible. Can you?
The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.
The first line of each test case contains two integers n and m (3 ≤ n, m ≤ 500), specifying the grid size, in which n is the number of rows and m is the number of columns.
Then n lines follow, each line contains m integers, giving the grid. All values in the grid are between 1 and 109 (inclusive).
For each test case, print a single line containing the minimum difference between the largest and smallest beauties after dividing the matrix into 4 parts.
## Input
The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.The first line of each test case contains two integers n and m (3 ≤ n, m ≤ 500), specifying the grid size, in which n is the number of rows and m is the number of columns.Then n lines follow, each line contains m integers, giving the grid. All values in the grid are between 1 and 109 (inclusive).
## Output
For each test case, print a single line containing the minimum difference between the largest and smallest beauties after dividing the matrix into 4 parts.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ n_k, m_k \in \mathbb{Z} $ denote the dimensions of the grid, with $ 3 \leq n_k, m_k \leq 500 $.
- Let $ G_k = (g_{i,j}^{(k)})_{1 \leq i \leq n_k,\ 1 \leq j \leq m_k} $ be the grid, where $ g_{i,j}^{(k)} \in \mathbb{Z} $ and $ 1 \leq g_{i,j}^{(k)} \leq 10^9 $.
**Constraints**
1. $ 1 \leq T \leq 100 $
2. For each $ k $:
- $ 3 \leq n_k, m_k \leq 500 $
- $ 1 \leq g_{i,j}^{(k)} \leq 10^9 $ for all $ i,j $
**Objective**
For each test case $ k $, choose integers $ x \in \{2, \dots, n_k-1\} $, $ y \in \{2, \dots, m_k-1\} $ to delete row $ x $ and column $ y $, partitioning the grid into four non-overlapping subgrids:
- Top-left: $ \{(i,j) \mid 1 \leq i < x,\ 1 \leq j < y\} $
- Top-right: $ \{(i,j) \mid 1 \leq i < x,\ y < j \leq m_k\} $
- Bottom-left: $ \{(i,j) \mid x < i \leq n_k,\ 1 \leq j < y\} $
- Bottom-right: $ \{(i,j) \mid x < i \leq n_k,\ y < j \leq m_k\} $
Let $ B_1, B_2, B_3, B_4 $ be the *beauties* (i.e., maximum values) of these four regions respectively.
Define $ D(x,y) = \max(B_1, B_2, B_3, B_4) - \min(B_1, B_2, B_3, B_4) $.
Find:
$$
\min_{\substack{2 \leq x \leq n_k-1 \\ 2 \leq y \leq m_k-1}} D(x,y)
$$