Longest Increasing Path in a Matrix

You are given a matrix (grid) of integers with R rows and C columns. Your task is to determine the length of the longest strictly increasing path in the grid. From any cell, you can move to any of its 8 adjacent neighbors. In other words, if you are currently at cell (r, c), your next move can be to the cell at (r+δ_r, c+δ_c) where δ_r, δ_c ∈ { -1, 0, 1 } and not both zero. The value in the next cell must be strictly greater than the current cell's value.

Formally, if you are at cell matrix[r][c] and move to matrix[r+δ_r][c+δ_c], then it must hold that:

$$matrix[r+δ_{r}][c+δ_{c}] > matrix[r][c]$$

Determine the maximum length of any path satisfying the above condition.

inputFormat

The first line of input contains an integer T, the number of test cases. Each test case is described as follows:

• The first line contains two integers R and C — the number of rows and columns in the matrix.
• This is followed by R lines, each containing C space-separated integers representing the matrix.

Input is read from standard input (stdin).

outputFormat

For each test case, output a single integer representing the length of the longest strictly increasing path in the matrix. Each result should be printed on a new line. Output is written to standard output (stdout).

## sample

1
3 3
1 2 3
6 5 4
7 8 9

9

</p>