F. 乌龟任务：机器人与地震 时间限制：每个测试点 3 秒 内存限制：256 MB

世界是一个有 $n$ 行和 $m$ 列的网格。行编号为 $0,1,\dots,n-1$，列编号为 $0,1,\dots,m-1$。在这个世界中，列是循环的（即每列中最上方和最下方的格子相邻）。位于第 $i$ 行、第 $j$ 列的格子（$0 \le i < n, 0 \le j < m$）记作 $(i, j)$。

在时间 $0$，格子 $(i, j)$（$0 \le i < n, 0 \le j < m$）要么有一块岩石，要么为空。格子 $(i, j)$ 的状态可以用整数 $a_{i,j}$ 描述：

• 如果 $a_{i,j} = 1$，则在 $(i, j)$ 处有一块岩石。
• 如果 $a_{i,j} = 0$，则在 $(i, j)$ 处没有岩石。

由于地震余波的影响，列受到板块运动的作用：每一列以每单位时间 $1$ 个格子的速度循环向上移动。形式化地说，对于某个 $0 \le i < n, 0 \le j < m$，如果当前时刻 $(i, j)$ 处有一块岩石，它会从 $(i, j)$ 移动到 $(i-1, j)$（如果 $i = 0$，则移动到 $(n-1, j)$）。

机器人 RT 最初位于 $(0, 0)$。它需要前往 $(n-1, m-1)$ 执行地震救援任务（到达右下角的格子）。地震不会改变机器人的位置，只会改变世界中岩石的位置。

设 RT 当前的位置为 $(x, y)$（$0 \le x < n, 0 \le y < m$），它可以执行以下操作：

• 循环向上移动一格，即从 $(x, y)$ 到 $((x+n-1) \bmod n, y)$，花费 $1$ 单位时间。
• 循环向下移动一格，即从 $(x, y)$ 到 $((x+1) \bmod n, y)$，花费 $1$ 单位时间。
• 向右移动一格，即从 $(x, y)$ 到 $(x, y+1)$，花费 $1$ 单位时间。（仅当 $y < m-1$ 时 RT 可以执行此操作）

注意：RT 不能向左移动，也不能停留在原地。

不幸的是，如果 RT 与岩石相撞，它会爆炸。因此，当 RT 在 $(x, y)$ 处，且 $((x+1) \bmod n, y)$ 或 $((x+2) \bmod n, y)$ 处有岩石时，RT 不能向下移动，否则会被岩石击中。

类似地，如果 $y+1 < m$ 且 $((x+1) \bmod n, y+1)$ 处有岩石，RT 不能向右移动，否则会被岩石击中。

然而，需要注意的是，如果在 $(x \bmod n, y+1)$ 和 $((x+1) \bmod n, y)$ 处有岩石，RT 仍然可以安全地向右移动。

请找出 RT 在不与任何岩石相撞的情况下到达 $(n-1, m-1)$ 所需的最短时间。如果无法到达，输出 $-1$。

输入 第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

在每个测试用例中，第一行包含两个整数 $n, m$（$3 \le n, m \le 10^3$）——世界边界的大小。

接下来的 $n$ 行中，每行包含 $m$ 个整数。第 $i+1$ 行（$0 \le i < n$）的第 $j+1$ 个整数（$0 \le j < m$）是 $a_{i,j}$（$0 \le a_{i,j} \le 1$），表示在时间 $0$ 时 $(i, j)$ 处是否有岩石。

此外，保证 $a_{0,0} = 0$，且对于 $0 \le i < n$，有 $a_{i, m-1} = 0$。也就是说，RT 的初始位置以及第 $m-1$ 列都没有岩石。

所有测试用例的 $n \cdot m$ 之和不超过 $10^6$。

输出 对于每个测试用例：

• 如果可以在不与任何岩石相撞的情况下到达目的地，输出一个整数——RT 到达 $(n-1, m-1)$ 所需的最短时间。
• 否则，输出 $-1$。

示例 输入 6 4 5 0 1 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 3 3 0 0 0 1 0 0 0 0 0 5 3 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 3 7 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 3 4 0 1 0 0 1 0 0 0 0 1 1 0 5 5 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 输出 7 3 3 8 -1 12

输入 6 3 3 0 0 0 0 0 0 0 0 0 4 3 0 1 0 1 0 0 0 1 0 1 0 0 4 3 0 1 0 0 1 0 0 1 0 0 1 0 3 3 0 0 0 1 1 0 0 0 0 3 3 0 1 0 0 0 0 0 1 0 5 5 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 输出 3 3 -1 -1 3 8 示例中第一个测试用例的直观解释（图示）：