405481: GYM101972 G Minimax

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Minimaxtime limit per test2.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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?

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.

ExampleInput
2
3 3
9 5 8
3 4 1
6 2 7
4 4
22 7 3 11
3 1 8 9
5 2 4 3
13 5 6 9
Output
3
13

加入题单

上一题 下一题 算法标签: