A11296. Turtle Mission: Robot and the Earthquake

The first line of the input contains one integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases.

In each test case, the first line contains two integers $n$ , $m$ ( $3 \le n, m \le 10^3$ ) — the size of the planet's boundaries.

Each of the next $n$ lines contains $m$ integers. The $(j+1)$ -th integer on the $(i+1)$ -th line ( $0 \le i < n, 0 \le j < m$ ) is $a_{i,j}$ ( $0 \le a_{i,j} \le 1$ ), which denotes whether or not there is a rock at $(i,j)$ at time $0$ .

Additionally, it is guaranteed that $a_{0,0} = 0$ , and $a_{i, m-1} = 0$ for $0 \le i < n$ . In other words, there is no rock at RT's initial position as well as column $m-1$ .

The sum of $n \cdot m$ over all test cases does not exceed $10^6$ .

For each test case:

- If the destination can be reached without colliding with any rocks, output a single integer — the minimum amount of time RT needs to reach $(n-1,m-1)$ .
- Otherwise, output $-1$ .

Visual explanation of the first test case in the example:


Visual explanation of the first test case in the example: