Problem Description

　　There is a King placed on an N * N chessboard. In each second, Bob must move the King to the next cell in one of the eight directions, but he can not move the King to the outside of the chessboard, and can not move the King to a damaged cell. Note: If and only if there is not any next cell that he can place the King on in the eight directions, the King will stay in the same cell.
Now your task is to calculate that, after T seconds, the number of the cells that the King could be on.

Input

　　There is an integer C (1 <= C <= 500) in the first line, indicates there are C test cases in total.
　　For each test case, there are four integers N (2 <= N <= 100), T (1 <= T <= 1000000000), X (1 <= X <= N), Y (1 <= Y <= N). N and T have the same meaning as above, (X, Y) indicates the King’s initial location. Then there are N lines. In each line, there is a string with N characters include “#” and “.”, which indicates the states of the cells in this row. “#” means this cell is damaged, and “.” means this cell is ordinary. You can assume (X, Y) is an ordinary cell.
　　For the coordinate (x, y), it stands for the cell in row x and column y. The coordinate of the top-left cell is (1, 1), and the coordinate of the bottom-right cell is (N, N).

Output

　　For each test case, you should output the correct answer of the above task in one line.

3
3 1 3 3
...
...
...
3 2 3 3
...
..#
.#.
3 4 1 3
.#.
.##
...

3
6
1

Hint

For Sample 1, the blue cells in the left picture of the Figure 1 show the cells that the King could be on after 1 second.
　　For Sample 2, the blue cells in the right picture of the Figure 1 show the cells that the King could be on after 2 seconds.
The red cells stand for the damaged cells, and the yellow cells shows other ordinary cells.