题目描述

小 Y 喜欢玩密室逃脱，每次游戏开始时，小 Y 会进入一个密室，她需要按照顺序解开各个隐藏线索才能成功逃脱密室。小 Y 非常聪明，解开线索对她来说并不难，但是她有一点懒，她希望在通关过程中移动次数最少。请你帮小 Y 计算她至少要移动多少次才能成功通关。

密室是 $m$ 行 $n$ 列的格子矩阵，小 Y 从左上角 $(1,1)$ 进入密室，密室中有三种格子：

• 墙，以数字 $0$ 标记；
• 路，以数字 $1$ 标记；
• 隐藏线索处，以数字 $( > 1)$ 标记, 代表该线索的难度。

小 Y 需要按照难度递增的顺序解开各个线索，逃脱密室。

输入格式

第一行是一个整数 $T$，表示输入包含 $T$ 组数据，分别是不同的游戏中小 Y 所处的密室。

对于每组数据，第一行包括两个整数：$m$（$1 \le m \le 100$）、$n$（$1 \le n \le 100$）。接下来 $m$ 行，每行有 $n$ 个数字，第 $i$ 行的第 $j$ 个数字表示密室中第 $i$ 行第 $j$ 列的格子的类型。题目保证进入密室处 $(1,1)$ 不是墙壁，线索的难度都不相同。

输出格式

对于每组数据，你需要输出一个整数，表示小 Y 在这个密室中至少要移动多少次才能成功通关。如果小 Y 不可能解开所有线索，输出 $-1$。

2
3 3
1 3 2
1 0 4
10 6 5
3 3
1 3 2
0 0 0
10 6 5

8
-1

由于需要按难度顺序解开线索，在第一组数据中，小 Y 第一次移动到 $3$ 时不能解密，在完成 $2$ 之后需要回到 $3$。最后小 Y 解开 $10$ 时，她成功通关。