题目描述

在一个 $n\times m$ 的 01 网格中，其中第 $i$ 行第 $j$ 列的元素为 $a_{i,j}$，若 $a_{i,j}=1$ 则表示这个位置为空地，反之若 $a_{i,j}=0$ 则表示这个位置上有障碍物。

现在小猫从 $(1,1)$ 出发，想要去 $(n,m)$。

若小猫当前在 $(x,y)$ 则一次移动后可以到 $(x-1,y)$、$(x+1,y)$、$(x,y-1)$、$(x,y+1)$、$(x-1,y-1)$、$(x+1,y-1)$、$(x-1,y+1)$、$(x+1,y+1)$ 的位置上，注意不能移动到地图外，也不能走到障碍物上。即任意时候 $1\leq x\leq n,1\leq y\leq m,a_{x,y}=1$。

因为小猫使用了难以控制的滑板火箭，每一分钟都会移动 $[l,r]$ 次。

现在需要你求出小猫最少需要几分钟才能成功抵达终点（必须要某一分钟的移动全部结束后小猫的位置在 $(n,m)$ 才算成功抵达），如果无论经过多久都不能成功抵达请输出 -1。

输入格式

第一行一个整数 $t$（$1\leq t\leq 1000$），表示测试数据组数。

接下来对于每一组测试数据，第一行两个整数 $n,m$（$2\leq n,m\leq 1000$），表示 01 网格的大小。

接下来一行包含两个整数 $l,r$（$1\leq l\leq r\leq 10^9$），表示在一分钟内移动次数的限制范围。

接下来 $n$ 行，每行 $m$ 个字符，表示网格的元素 $a_{i,j}$，字符仅会出现 0 或 1，且 $a_{1,1}$ 与 $a_{n,m}$ 一定为 $1$。

保证所有测试数据的 $n\times m$ 的和不超过 $10^6$。

输出格式

对于每一组测试数据输出一行，如果小猫能在有限时间内抵达 $(n,m)$，那么输出最少需要的分钟数，否则输出 -1。

3
5 5
2 3
10000
01000
00110
11001
11111
7 8
3 3
10101000
01010100
10000100
01000010
00100100
00011010
00000001
7 8
4 4
10101000
01010100
10000100
01000010
00100100
00011010
00000001

2
3
3

提示

对于第一组样例：

在第一分钟 $(1,1)\rightarrow (2,2)\rightarrow (3,3)\rightarrow (3,4)$；

在第二分钟 $(3,4)\rightarrow (4,5)\rightarrow (5,5)$。