Cave Exploration

Time limit1sMemory limit128 MB

Summary

Simulate a maze-runner who always turns left when possible on a grid of horizontal and vertical corridors until he returns to the start, then count unvisited corridors.

Level: Medium7 of 10
Topics: Simulation, Geometry, Implementation
Solved: No attempts yet

Problem

An explorer claims to have walked through every corridor of a cave. Each corridor is a straight horizontal or vertical segment. A corridor counts as visited if the explorer stood at (passed through) at least one of its points. Your task is to check the claim by simulating the explorer's route and counting how many corridors were never visited.

The explorer starts at a given entry point, facing a given direction, and always applies the same rule at every point where his route could change direction: he turns left if he can; otherwise he goes straight; otherwise he turns right; otherwise he turns back. Being able to go in a direction means a corridor continues from the current point in that direction. Left and right are relative to his current heading, where turning left is a $90^\circ$ counter-clockwise turn (facing east, left is north; facing north, left is west; facing west, left is south; facing south, left is east). The exploration ends the instant he returns to the entry point for the second time (being placed there at the start counts as the first time).

No two vertical corridors share a common point, and no two horizontal corridors share a common point; a horizontal and a vertical corridor may cross or touch. The entry point never lies at the intersection of two corridors, and the explorer can always move in the given starting direction.

Input

The first line contains an integer $T$ ( $T \le 20$ ), the number of maps. Each map is given as follows.

The first line contains an integer $N$ ( $N \le 1000$ ), the number of corridors. There are at most $500$ vertical corridors and at most $500$ horizontal corridors.
Each of the next $N$ lines describes one corridor. A horizontal corridor is given as H followed by one $y$ -coordinate and two $x$ -coordinates. A vertical corridor is given as V followed by one $x$ -coordinate and two $y$ -coordinates.
The last line of the map contains the entry point's $x$ and $y$ coordinates and the starting direction, one of W (west, $-x$ ), E (east, $+x$ ), N (north, $+y$ ), S (south, $-y$ ).

All coordinates are integers whose absolute value does not exceed $32767$ .

Output

For each map, print on its own line the number of corridors that the explorer never visited.

Notes

Illustration of the cave in the first example

The figure illustrates the cave described in the first map of the first example.

Examples1

Example 1

Input

Expected output

1
0