In an $n \times m$ grid, the element at row $i$ and column $j$ is $a_{i,j}$. If $a_{i,j} = 1$, this position is an empty space; if $a_{i,j} = 0$, there is an obstacle at this position.

A kitten starts at $(1, 1)$ and wants to reach $(n, m)$.

If the kitten is currently at $(x, y)$, it can move to $(x-1, y), (x+1, y), (x, y-1), (x, y+1), (x-1, y-1), (x+1, y-1), (x-1, y+1),$ or $(x+1, y+1)$ in one move. Note that it cannot move outside the map, nor can it move onto an obstacle. That is, at any time, $1 \le x \le n, 1 \le y \le m,$ and $a_{x,y} = 1$.

Because the kitten is using an uncontrollable hover-rocket, it will move between $l$ and $r$ times every minute.

You need to find the minimum number of minutes required for the kitten to successfully reach the destination. (The kitten is considered to have successfully reached the destination only if its position is $(n, m)$ at the end of all moves in a given minute.) If it is impossible to reach the destination regardless of how much time passes, output -1.

Input

The first line contains an integer $t$ ($1 \le t \le 1000$), representing the number of test cases.

For each test case, the first line contains two integers $n, m$ ($2 \le n, m \le 1000$), representing the size of the 01 grid.

The next line contains two integers $l, r$ ($1 \le l \le r \le 10^9$), representing the range of the number of moves allowed in one minute.

The next $n$ lines, each containing $m$ characters, represent the elements $a_{i,j}$ of the grid. The characters are only 0 or 1, and $a_{1,1}$ and $a_{n,m}$ are guaranteed to be 1.

It is guaranteed that the sum of $n \times m$ over all test cases does not exceed $10^6$.

Output

For each test case, output one line. If the kitten can reach $(n, m)$ within a finite amount of time, output the minimum number of minutes required; otherwise, output -1.

Examples

Input 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

Output 1

2
3
3

Note

For the first example: In the first minute: $(1, 1) \to (2, 2) \to (3, 3) \to (3, 4)$; In the second minute: $(3, 4) \to (4, 5) \to (5, 5)$.