Minimum Jumps to Reach the End in a Grid

You are given a 2D grid of size \(N \times M\) where each cell \(A[i][j]\) contains a positive integer indicating the exact jump distance that can be made from that cell. From a cell \((i, j)\), you may jump exactly \(k = A[i][j]\) steps in any of the four cardinal directions: up, down, left, or right. Formally, if you are at cell \((i, j)\) with jump value \(k\), you can move to:

• \((i + k, j)\)
• \((i - k, j)\)
• \((i, j + k)\)
• \((i, j - k)\)

Your task is to determine the minimum number of jumps required to move from the top-left cell (\((0,0)\)) to the bottom-right cell (\((N-1, M-1)\)). If it is impossible to reach the destination, output \(-1\). Note that if the grid consists of a single cell, you are already at the destination, so the required number of jumps is \(0\).

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(T\), the number of test cases. Each test case is formatted as follows:

• The first line contains two integers \(N\) and \(M\), representing the grid dimensions.
• The next \(N\) lines each contain \(M\) space-separated integers, representing the grid \(A\).

All values are positive integers (except for the special 1x1 grid cases, where the number may be 0 or 1).

outputFormat

For each test case, print a single line to standard output (stdout) containing the minimum number of jumps required to reach the bottom-right cell. If the destination is unreachable, output \(-1\).

## sample

2
3 3
2 3 1
1 2 2
1 1 1
2 2
2 1
1 0

3
-1

</p>