Problem Description

FJ becomes interested in ice-skating these days. Every weekends, he goes to the rink in his town. The rink is a rectangle that made up of r rows and c colomns of small squares. Some of squares are damaged and skating on these squares are forbidden.

FJ is a beginner, and he can only do a sequence of k actions one after another. One action means skating forward at most l squares (Doesn't include the square he start at) in a certain direction (Up, Down, Left and Right). Notice that he can't skate on broken squares.

Now the problem is: Given the rink and the sequence of actions, how long can FJ skating at most.

Input

The first line of input file is a single integer T (1 ≤ T ≤ 10) - the number of test cases. For each test case, in the first line there are 5 integers: r, c, x, y, k. The meaning of r, c and k are described as above. x and y means FJ is at the square in the x-th row (counting from the top and start from 1) and y-th colomn (counting from the left side and start from 1). Then there are r lines, describing the rink - '.' means good squares, and 'x' means broken squares. Then there are k lines, giving the k actions in order. Each of these lines contain 2 integers: l and d, d ∈ {1, 2, 3, 4}, 1 represent upward, 2 represent left, 3 represent downward and 4 represent right.

(1 ≤ r, c ≤ 200; 1 ≤ k ≤ 200);

Output

Output a single integer, the maxmum number of square FJ can skate throuth. If FJ skates through a square twice, count twice.

1
4 5 4 1 3
..xx.
.....
...x.
.....
3 4
2 1
2 2

6

Hint

For the sample input, FJ can skate in this way: