There is a virus outbreak in a country. Some cities are infected with virus and some are not. In some cities vaccine production has started. We are representing the country using a 2D grid where each cell can be an infected city represented with ‘-’ or an uninfected city represented with ‘.’ or a vaccine producing city represented with ‘+’.
It takes S days for the virus to spread to the adjacent cities(cities sharing a common side). For the vaccine we just need 1 day to take it to the adjacent cities but to take effect it needs E days, until then that city can infect other cities.
You need to calculate how many cities will still be infected after D days. (infected cities which are not completely immunized).
Note: When the vaccine completes its effect the city cannot spread virus from that day onwards.
Input Format
First line contains an integer T - Number of test cases.
First line of each test case contains 2 space separated integers N, M - Number of rows and columns in the grid.
Next N lines, each containing M characters.
Last line of a test case contains 3 space separated integers E, S, D - Number of days required for the vaccine to take effect, number of days required for the virus to spread and number of days after which you have to find the result.
Constraints
T <= 100
1 <= N, M <= 500
1 <= E, S, D <= 10^3
Sum of N*M over all test cases doesn’t exceed 10^6.
Output Format
For each test case, print the number of cities which are still infected after D days in a separate line.
Sample Input 0
2
3 4
.-…
.-…
+…
3 2 5
3 3
-…
…-
.+.
2 2 4
Sample Output 0
5 2
Explanation 0
In the first test case, the cities {0,2}, {1,2} gets infected after 2 days and the cities {0,3}, {1,3} gets infected after 4 days. These 4 cities and the city {0,1} are still infected after 5 days. Note: The city {1,1} gets immunized after 5 days so it does not count to our total.
In the second test case, the cities {0,0} and {0,2} are infected. Note: These cities have received the vaccine but its effect has not started yet.
