Little W is exploring an $n \times n$ map containing empty spaces and obstacles. Empty spaces are represented by . and obstacles by #. Little W needs to travel from a starting point to a destination. During this process, he fails if he hits an obstacle or moves outside the boundaries of the map.

Little W has a movement sequence of length $m$ to reach the destination. Let $(x, y)$ be Little W's current position. In the next step, Little W can move to $(x + u, y + v)$ or stay in the same position. Note that staying in the same position counts as one step. $u$ and $v$ are any integers in $[-1, 1]$. For various reasons, Little W cannot use certain $(u, v)$ pairs in each step. For the $i$-th step, whether a specific $(u, v)$ pair can be used is represented by a binary string $s_i$ of length $8$. The eight constrained $(u, v)$ pairs are: $(-1, -1)$, $(-1, 0)$, $(-1, 1)$, $(0, -1)$, $(0, 1)$, $(1, -1)$, $(1, 0)$, and $(1, 1)$.

There are $q$ queries. Each query asks whether Little W can travel from $(x_1, y_1)$ to $(x_2, y_2)$ within $m$ steps without hitting any obstacles. If possible, output the minimum number of steps required to reach $(x_2, y_2)$ (staying in the same position counts as a step). If not possible, output $-1$.

Input

This problem contains multiple test cases. The first line contains two positive integers $c$ and $t$, representing the subtask ID and the number of test cases, respectively. Specifically, for the sample, $c = 0$.

For each test case:

• The first line contains five positive integers $n, m, q, x_1, y_1$.
• The next $n$ lines each contain a string of length $n$, representing the type of each coordinate on the initial map.
• The next $m$ lines each contain a string $s_i$ of length $8$, representing the constraints for the $i$-th step.
• The next $q$ lines each contain two positive integers $x_2, y_2$.

Output

For each test case:

• Output $q$ lines, each containing an integer representing your answer.

Examples

Input 1

0 1
3 4 5 2 2
...
...
...
00001000
00000010
00001000
01000000
2 3
1 3
1 2
3 2
1 1

Output 1

1
4
4
2
-1

Note 1

For the first query of the test case, moving from $(2, 2)$ to $(2, 3)$ in the first step satisfies the requirement. It can be proven that this is the minimum number of steps required.

For the second query, moving from $(2, 2)$ to $(2, 3)$ in the first step, staying in the same position for the second and third steps, and moving from $(2, 3)$ to $(1, 3)$ in the fourth step satisfies the requirement. It can be proven that this is the minimum number of steps required.

Constraints

For all data, it is guaranteed that:

• $1 \le t \le 10^5$;
• $1 \le n \le 3000$;
• $1 \le m, q \le 10^5$;
• $\sum n^2 \le 3000^2$;
• $\sum m, \sum q \le 10^6$.

This problem uses bundled testing. The special properties of each subtask are as follows: