海龟任务：机器人与地震

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

有一个 $n$ 行 $m$ 列的网格，行和列均从 $0$ 编号。上下边界循环相邻。初始时 $a_{i,j}=1$ 表示格 $(i,j)$ 有石头，否则为空。每经过一单位时间，所有石头循环向上移动一格。

机器人初始位于 $(0,0)$，目标是 $(n-1,m-1)$。每单位时间它必须执行一次操作：循环向上、循环向下，或在尚未到达末列时向右。

机器人位于 $(x,y)$ 时：若当前的 $((x+1)\bmod n,y)$ 或 $((x+2)\bmod n,y)$ 有石头，则不能向下；若 $((x+1)\bmod n,y+1)$ 有石头，则不能向右。向上总是允许。求到达目标的最少时间；无法到达输出 $-1$。

输入格式

第一行一个整数 $t$。每组先输入 $n,m$，随后输入 $n$ 行、每行 $m$ 个整数的矩阵 $a$。

保证 $a_{0,0}=0$，末列均为零。

输出格式

每组输出最少时间或 $-1$。

样例输入

3
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
3 4
0 1 0 0
1 0 0 0
0 1 1 0

样例输出

7
3
-1

数据范围

对于所有数据，$1\le t\le10^4$，$3\le n,m\le10^3$，且所有测试用例的 $n\cdot m$ 之和不超过 $10^6$。