当前没有测试数据。

弹珠游戏

题目描述

小 $A$ 和同学们一起玩他们自己设计的弹珠游戏。

游戏在一个矩形棋盘上进行，棋盘上有一些位置是空地，有一些位置是障碍，并设有起点和终点，起点和终点确保没有障碍。游戏的目标是​通过最少的发射次数​，将弹珠从起点移动到终点。

弹珠在游戏开始时，放在起点位置，游戏规则如下：

1. 弹珠只能上下左右直线移动，不能沿对角线移动，更不能移出棋盘；
2. 你可以向弹珠四方向中的没有障碍的格子发射弹珠（如上图 a 所示）。弹珠发射出去后沿直线移动。

弹珠发射后沿直线移动，停止的条件为：

1. 遇到障碍，弹珠停止在障碍前，障碍被碰撞后消失。如上图 b 所示，碰撞障碍后，障碍消失，弹珠停下，呈现出上图 c 所示的状态。
2. 遇到终点，弹珠停止在终点上，游戏结束。

如下图 a 所示，展现了弹珠经过 $4$ 次发射到达终点的轨迹。下图 b 展示了弹珠到达终点后，棋盘的空地和障碍的状态变化。

为了防止游戏时间过长，游戏有一个特别的规定，在游戏中，你不能发射弹珠超过 $10$ 次，如果发射弹珠超过 $10$ 次则视为无法到达终点。

请编程计算出，弹珠从起点到终点，最少要发射的次数。如果弹珠无论如何都无法走到终点，请输出 $−1$。

输入

本题有多组测试数据。

第 $1$ 行读入一个整数 $T$，代表测试数据组数。

对于每组测试数据，第 $1$ 行读入两个整数 $W$ 和 $H$，代表了棋盘的宽度和高度。

接下来 $H$ 行，每行有 $W$ 个数字，代表了棋盘的初始状态，棋盘中数字含义如下。

$0$：代表空地。

$1$：代表障碍物。

$2$：代表起点。

$3$：代表终点。

输出

输出 $T$ 行，针对每组测试数据，输出按题意计算的结果。

样例

输入复制

6
2 1
3 2
6 6
1 0 0 2 1 0
1 1 0 0 0 0
0 0 0 0 0 3
0 0 0 0 0 0
1 0 0 0 0 1
0 1 1 1 1 1
6 1
1 1 2 1 1 3
6 1
1 0 2 1 1 3
12 1
2 0 1 1 1 1 1 1 1 1 1 3
13 1
2 0 1 1 1 1 1 1 1 1 1 1 3

输出复制

1
4
-1
4
10
-1

说明

样例解释

样例 $1$ 中的第 $2$ 组测试数据，所呈现的$6×6$ 的矩阵，就是题目描述中所画的经过 $4$ 次发射到达终点的示例。

数据范围

对于 $100$% 的测试数据 $1≤T≤25$，$1≤W,H≤20$。