#P1695A. Subrectangle Guess

Subrectangle Guess

Description

Michael and Joe are playing a game. The game is played on a grid with nn rows and mm columns, filled with distinct integers. We denote the square on the ii-th (1in1\le i\le n) row and jj-th (1jm1\le j\le m) column by (i,j)(i, j) and the number there by aija_{ij}.

Michael starts by saying two numbers hh (1hn1\le h \le n) and ww (1wm1\le w \le m). Then Joe picks any h×wh\times w subrectangle of the board (without Michael seeing).

Formally, an h×wh\times w subrectangle starts at some square (a,b)(a,b) where 1anh+11 \le a \le n-h+1 and 1bmw+11 \le b \le m-w+1. It contains all squares (i,j)(i,j) for aia+h1a \le i \le a+h-1 and bjb+w1b \le j \le b+w-1.

Possible move by Joe if Michael says 3×23\times 2 (with maximum of 1515).

Finally, Michael has to guess the maximum number in the subrectangle. He wins if he gets it right.

Because Michael doesn't like big numbers, he wants the area of the chosen subrectangle (that is, hwh \cdot w), to be as small as possible, while still ensuring that he wins, not depending on Joe's choice. Help Michael out by finding this minimum possible area.

It can be shown that Michael can always choose h,wh, w for which he can ensure that he wins.

Each test contains multiple test cases. The first line contains the number of test cases tt (1t201 \le t \le 20). Description of the test cases follows.

The first line of each test case contains two integers nn and mm (1n,m401 \le n, m \le 40)  — the size of the grid.

Each of the following nn lines contains mm integers. The jj-th integer on the ii-th line is aija_{ij} (109aij109-10^9 \le a_{ij} \le 10^9)  — the element in the cell (i,j)(i, j).

It is guaranteed that all the numbers are distinct (that is, if ai1j1=ai2j2a_{i_1j_1} = a_{i_2j_2}, then i1=i2,j1=j2i_1 = i_2, j_1 = j_2).

For each test case print a single positive integer  — the minimum possible area the subrectangle can have while still ensuring that Michael can guarantee the victory.

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1t201 \le t \le 20). Description of the test cases follows.

The first line of each test case contains two integers nn and mm (1n,m401 \le n, m \le 40)  — the size of the grid.

Each of the following nn lines contains mm integers. The jj-th integer on the ii-th line is aija_{ij} (109aij109-10^9 \le a_{ij} \le 10^9)  — the element in the cell (i,j)(i, j).

It is guaranteed that all the numbers are distinct (that is, if ai1j1=ai2j2a_{i_1j_1} = a_{i_2j_2}, then i1=i2,j1=j2i_1 = i_2, j_1 = j_2).

Output

For each test case print a single positive integer  — the minimum possible area the subrectangle can have while still ensuring that Michael can guarantee the victory.

Samples

样例输入 1

3
1 1
3
4 4
2 12 6 10
3 15 16 4
1 13 8 11
14 7 9 5
2 3
-7 5 2
0 8 -3

样例输出 1

1
9
4

Note

In the first test case, the grid is 1×11\times 1, so the only possible choice for h,wh, w is h=1,w=1h = 1, w = 1, giving an area of hw=1h\cdot w = 1.

The grid from the second test case is drawn in the statement. It can be shown that with h=3,w=3h = 3, w = 3 Michael can guarantee the victory and that any choice with hw8h\cdot w \le 8 doesn't.