Walls and Gates

You are given a 2D grid that represents a map of rooms, walls, and gates. Each cell in the grid can be:

• -1 representing a wall which you cannot pass through.
• 0 representing a gate.
• 2147483647 (representing infinity) representing an empty room. You can assume that 2147483647 is used for empty rooms.

Your task is to fill each empty room with the number of steps to reach its nearest gate. If it is impossible for an empty room to reach any gate, leave it as 2147483647.

You are required to use an efficient algorithm (e.g., Breadth-First Search) to solve the problem.

inputFormat

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

1. The first line contains a single integer T representing the number of test cases.
2. For each test case, the first line contains two space-separated integers m and n which denote the number of rows and columns of the grid respectively.
3. This is followed by m lines, each containing n space-separated integers. Each integer will be either -1, 0, or 2147483647.

outputFormat

For each test case, output the modified grid to standard output (stdout) in the following format:

1. Output m lines where each line contains n space-separated integers representing the final state of the grid after filling the empty rooms with the distance to the nearest gate.
2. The order of the test cases in the output should be the same as in the input.

## sample

4
4 4
2147483647 -1 0 2147483647
2147483647 2147483647 2147483647 -1
2147483647 -1 2147483647 -1
0 -1 2147483647 2147483647
2 2
0 -1
-1 0
2 2
-1 -1
-1 -1
2 2
2147483647 0
2147483647 0

3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4
0 -1
-1 0
-1 -1
-1 -1
1 0
1 0

</p>