Rotting Oranges

You are given a 2D grid of dimensions n\times m representing oranges. Each cell in the grid can have one of three values:

• 0: An empty cell.
• 1: A fresh orange.
• 2: A rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent (up, down, left, right) to a rotten orange becomes rotten. The task is to determine the minimum number of minutes that must elapse until no fresh orange remains. If it is impossible for all oranges to become rotten, the answer should be -1.

This can be modeled using a breadth-first search (BFS) where each minute represents one level of traversal. The spreading process can be summarized by the following formula in LaTeX: $$\text{minutes} = \min\{ t \;|\; \text{all fresh oranges are rotten at time } t \}$$ If not all fresh oranges can be reached, then the answer is \(-1\).

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains an integer T representing the number of test cases.
2. For each test case:
   • The first line contains two integers n and m — the number of rows and columns respectively.
   • The next n lines each contain m space-separated integers (each being 0, 1, or 2), representing the grid.

outputFormat

For each test case, output a single integer on a new line to standard output (stdout). This integer is the minimum number of minutes required for all fresh oranges to become rotten. If it is impossible, output -1.

## sample

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

4

</p>