Longest Increasing Path
Algorithms
Approved
Dynamic programming
Medium
Open
Two dimensional
86.0% success
6,525 attempts
1s time
256MB memory
1024KB max code

There is a 2D matrix of N rows and M columns. Rows are number 1 to N from top to bottom and columns 1 to M from left to right. You are standing at (1,1).

From, A [ i ] [ j ] you can move to A [ i + 1 ] [ j ] if A [ i + 1 ] [ j ] > A [ i ] [ j ]. Or, from, A [ i ] [ j ] you can move to A [ i ] [ j + 1 ] if A [ i ] [ j + 1 ] > A [ i ] [ j ].

Moving from (1,1), what is the longest path that you can travel?

Input:
First line contains, T, the number of testcases. Each testcase consists of N, M. Each of the next N lines contain M integers each.

Output:
For each testcase, print the length of the longest path from (1,1).

Constraints:
1 ≤ T ≤ 100
1 ≤ N, M ≤ 100
1 ≤ A[i][j] ≤ 106

Examples
Input
3
1 1
1
4 4
1 2 3 4
2 2 3 4
3 2 3 4
4 5 6 7
2 2
1 2
3 4
Output
1
7
3
Explanation

In first testcase the path is of 1 length only i.e. (1,1). In second testcase, the path of length 7 is (1,1) , (2,1), (3,1), (4,1), (4,2), (4,3), (4,4). In third case, any of the following paths can be taken. (1,1), (1,2), (2,2) or (1,1), (1,2), (2,2). Both are of length 3.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading Editor...