Minimum Moves to Reach End in a Grid

You are given an N x N grid where each cell is either empty (denoted by 0) or contains an obstacle (denoted by 1). A robot starts at the top-left cell (0, 0) and must reach the bottom-right cell (N-1, N-1). The robot can move one cell at a time in one of the four cardinal directions: up, down, left, and right. It cannot move diagonally or go outside the grid boundaries.

Your task is to calculate the minimum number of moves required for the robot to reach the destination. If it is impossible to reach the destination, output -1.

You can model the problem using a breadth-first search (BFS). In mathematical notation, given a grid \(A\) where \(A_{ij}\) represents the cell at row \(i\) and column \(j\), we need to find the minimum number of steps to move from \((0, 0)\) to \((N-1, N-1)\) following only adjacent moves. The move count can be denoted by:

[ \text{moves} = \min_{\text{path}} {\text{number of steps}} ]

If no such path exists, the answer is \(-1\).

inputFormat

The input is read from standard input (stdin) and consists of multiple test cases. The first line contains an integer T denoting the number of test cases. For each test case:

• The first line contains an integer N representing the size of the grid.
• Then follow N lines, each containing N space-separated integers (either 0 or 1) representing the grid.

For example:

1
4
0 0 0 0
1 1 0 1
0 0 0 0
0 1 1 0

outputFormat

For each test case, output a single integer on a new line: the minimum number of moves required for the robot to reach the bottom-right corner, or -1 if it is impossible.

The output is written to standard output (stdout).

## sample

1
4
0 0 0 0
1 1 0 1
0 0 0 0
0 1 1 0

6

</p>