Longest Increasing Snake Path

Given a grid of integers, your task is to determine the length of the longest snake path in the grid. A snake path is defined as a sequence of adjacent cells (up, down, left, or right) that has strictly increasing values. More formally, for a grid (A) of size (n \times m), you need to find the maximum length of a path (A_{i_1,j_1}, A_{i_2,j_2}, \ldots, A_{i_k,j_k}) such that for every (1 \leq t < k), the cells ((i_t,j_t)) and ((i_{t+1},j_{t+1})) are adjacent and (A_{i_t,j_t} < A_{i_{t+1},j_{t+1}}).

Note: Two cells are considered adjacent if they share a common edge.

inputFormat

The input is given from standard input (stdin). The first line contains an integer (T) representing the number of test cases. For each test case, the first line contains two integers (n) and (m) denoting the number of rows and columns of the grid respectively. This is followed by (n) lines, each containing (m) space-separated integers representing the grid.

outputFormat

For each test case, output a single integer denoting the length of the longest increasing snake path in the corresponding grid. The output for each test case should be written to standard output (stdout) on a new line.## sample

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

9