MXSBMTRX - Largest Increasing Sub-Matrix

Mosa loves all sorts of properties of matrices. One day his coach Fegla asked him to draw a matrix with size N × M and insert random numbers in each cell, then he asked him to find the largest increasing sub-matrix.

It's defined as a matrix that each cell in the position (i, j) is greater than the cells in positions:

(i - 1, j), (i, j - 1) and (i - 1, j - 1).

Maximum increasing sub-matrix

Help Mosa to find the size of the largest increasing sub-matrix.

Input

t - the number of test cases, then t test cases follows. [t <= 50]

Each test case contains two integers N and M indicating the matrix dimensions [1 <= N * M <= 105].

Each of the next N lines contains M integers, separated by a space, describing the elements of the matrix.

Element Xi,j of the matrix is the jth integer of the ith line in the input [-109 <= Xi,j <= 109].

Output

For each test case in the input your program must print on single line, containing the solution of the problem.

Example

Input:
2
2 3
2 2 2
2 2 2 3 3
1 2 5
4 6 7
10 8 3 Output: 1
6

Added by:eagle93
Date:2014-02-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2023-10-17 02:38:55 Oleg
See also https://www.spoj.com/problems/NPC2014H/
2014-05-28 17:46:07 eagle93
@Aditya Deepak: Yes, n could be 10^5, m = 1 and vice versa.
You can allocate dynamic array not fixed!
2014-05-23 11:42:56 adijimmy
what are the constraints for the value of n and m ?? admin please reply as its too vague as n*m<=10**5 as in this case maximum and minimum value of n,m can be 10**5 and 1 and if this is so we cant allocate so much memory :(
2014-03-21 14:04:04 eagle93
@Apoorv Jindal:
It'll be 4
the size of sub-matrix is 1×4
2014-03-06 09:51:38 Apoorv Jindal
The problem statement is ambiguous! What will be the output for:
1
3 4
10 10 10 10
10 1 2 10
10 3 4 10
Will the output be 1 or 4?

Last edit: 2014-03-06 09:52:10
2014-02-17 07:28:35 Jacob Plachta
Alright, thanks!
2014-02-17 06:52:27 eagle93
@Jacob Plachta: It's my fault!
I rejudged all submissions.
Thank you :)
2014-02-16 22:24:06 Jacob Plachta
Was the data definitely uploaded correctly? I've tested my code on a large number of random cases with a brute-force checker.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.