Longest Straight Line Path in a Grid

You are given a 2D grid of integers representing elevation values. Your task is to compute the length of the longest straight line path that is either strictly increasing or strictly decreasing. You can move in any of the following four directions:

• Right: \( (0, 1) \)
• Down: \( (1, 0) \)
• Diagonal Down-Right: \( (1, 1) \)
• Diagonal Up-Right: \( (-1, 1) \)

For each test case, you will be given the dimensions of the grid and the grid values. For every cell, in each of the four allowed directions, determine the longest path that can be formed where the consecutive cells are either strictly increasing or strictly decreasing. Print the maximum path length found for each test case.

Note: A path must move along one of the four allowed directions only, and you can start from any cell.

inputFormat

The input begins with a single integer \( T \) denoting the number of test cases. For each test case, the first line contains two integers \( N \) and \( M \) representing the number of rows and columns, respectively. This is followed by \( N \) lines, each containing \( M \) space-separated integers representing the grid values.

Input is read from standard input (stdin).

outputFormat

For each test case, output a single integer on a new line, representing the length of the longest strictly increasing or strictly decreasing path in one of the specified straight directions.

Output should be written to standard output (stdout).

## sample

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

3

</p>