The Trojan Horse

Interview

Time limit1sMemory limit256 MB

Summary

Mark all cells visited by patrol routes on an h by w grid, then count 4-connected unvisited regions with at least s cells.

Level: Easy3 of 10
Topics: DFS, Simulation, Matrix
Solved: No attempts yet

Problem

After the Trojan War, the Greek army left a giant wooden horse and pretended to sail away. The Trojans pulled the horse inside their walls without checking it, and soldiers hidden inside opened the gates.

In this problem you do what the Trojans should have done. Given patrol routes through the horse, count how many unvisited connected regions are large enough to hide one Greek soldier of size s cells.

The horse is an h by w rectangular grid. Each Trojan soldier starts at the bottom-left cell and walks according to a string of moves l, r, u, d (left, right, up, down). Every visited cell counts as patrolled. An unpatrolled region connected by the four cardinal directions is a cavity. Soldiers are flexible, so a cavity with at least s cells can hide one soldier.

Input

The first line contains K, the number of test data sets.

Each data set begins with four integers h, w, s, n separated by spaces. h and w are the grid height and width (1 ≤ h, w ≤ 30), s is the soldier size in cells (1 ≤ s ≤ hw), and n is the number of patrolling soldiers (1 ≤ n ≤ 100).

The next n lines each contain one patrol route, a string of at most 100 characters from l, r, u, d. Every soldier starts at the bottom-left cell and never leaves the grid.

Output

For each data set, print Data Set x: on its own line (x starts at 1), then on the next line print the number of cavities whose size is at least s. Print a blank line after each data set.

Examples3

Example 1

Input

2
4 4 2 2
uuurrdurdddll
urdlrr
10 10 4 2
uuuuuuuuurrrrrrrrrdddddddddlllllllllrruuuuuuuuu
uuurrrrrrrrruuulldlld

Expected output

Data Set 1:
0

Data Set 2:
4

Example 2
Input
```
1
1 1 1 1
```
Expected output
```
Data Set 1:
0
```
Example 3
Input
```
1
2 2 1 1
r
```
Expected output
```
Data Set 1:
1
```