Longest Increasing Path in a Matrix

You are given an M x N integer matrix. Your task is to find the length of the longest increasing path in the matrix.

From any cell, you can move in four directions: left, right, up, and down. You may only move to a cell with a strictly greater value than the current one. In other words, if the current cell contains a value \(a\) and a neighboring cell contains \(b\), you can move from \(a\) to \(b\) only if \(b > a\).

The length of a path is the number of cells visited. You are required to consider all possible starting positions and compute the overall longest increasing path in the matrix.

Note: The algorithm should be efficient enough to handle moderately sized matrices.

For example, given the matrix:

9 9 4
6 6 8
2 1 1

the longest increasing path is of length 4.

inputFormat

The first line contains an integer T representing the number of test cases.

For each test case, the first line contains two integers M and N representing the number of rows and columns of the matrix respectively. This is followed by M lines each containing N space-separated integers representing the matrix.

Input Format:

T
M N
row1
row2
...
rowM

outputFormat

For each test case, output one integer representing the length of the longest increasing path in the matrix.

Each answer should be printed on a new line.

## sample

3
3 3
9 9 4
6 6 8
2 1 1
1 1
1
2 2
1 2
4 3

4
1
4

</p>