In Defence of a Garden

They say necessity is the mother of invention, but for some people laziness is the more likely parent.

Hubert Greenthumb hated digging fence posts, yet he knew that without a fence around his garden the deer from the nearby woods would eat his vegetables before he could harvest them.

A bit of a tinkerer, he built an Automatic Garden Fence Layer from a small garden tractor, some outdated computer chips, and a pair of robot arms. You program in the fence shape you want and the machine chugs around the yard, laying fence in 1-foot sections until the job is done.

Hubert told the machine to enclose a 25-by-25-foot square inside his 100-by-100-foot yard, started it, and went inside. When he came back, the machine had laid fence along an elaborate, seemingly random walk. Rather than admit anything had gone wrong, he decided to garden whatever the machine had actually enclosed. Any part of the yard the deer can no longer reach (fully enclosed by fence) counts as garden.

To buy the right amount of seed he needs the enclosed area. Given the robot's starting point and its sequence of moves, compute how many square feet are enclosed.

The yard is a 100 x 100 grid of 1-foot cells. The robot travels along the edges of the grid, building a fence from grid vertex to grid vertex. Because the fence lies exactly on grid edges, it occupies no area: for example, if the robot moves North 1, East 1, South 1, and West 1, it encloses exactly 1 square foot.

The first line contains the number of data sets. There are no blank lines between data sets.

Each data set begins with a line of three integers X Y Z: the starting position (X, Y) on the grid and the number Z of moves. X is the distance in feet from the western edge and Y the distance from the southern edge; both are between 0 and 100 inclusive.

The next Z lines each contain a direction character D (one of N, S, E, W) and an integer F separated by a space, meaning the robot travels F feet in direction D.

The path never leaves the 100 x 100 yard. It may or may not be closed, and it may cross itself or retrace edges it has already fenced (retracing lays no new fence).

For each data set, print one line:

Data Set N: Q square feet.

where N is the data set number starting from 1 and Q is the number of square feet enclosed by the fence. After the last data set, print End of Output on a line by itself.