Slithering Serpent

Zakhar is playing a version of the Snake game on an infinite grid, using an infinitely long snake, to get more comfortable with the idea of infinity. The snake starts as a single square at an arbitrary location. On each move the snake grows by one square: the player chooses an empty square that is horizontally or vertically adjacent to the current head, and that square becomes the new head. The tail never moves — once the snake occupies a square, some part of the snake stays there forever. Zakhar loves the endless playability of this game.

Zakhar occasionally has brief absence seizures that last only a few moments, and he never notices them. His little sister, Alyona, wants to play a trick on him during one of these lapses. She wants to steer the snake into a position from which it is doomed: the snake has not crashed yet, but no matter how it is played afterwards it is guaranteed to crash into itself after some finite number of additional moves. Alyona must act as quickly as possible, because Zakhar could come out of the seizure at any moment.

The input contains several test cases. Each test case begins with a line containing a single integer $T$, the number of moves the snake made before Zakhar's absence seizure. The next line contains $T$ pairs. Each pair is a positive integer $R$ followed by one character from the set {N, E, W, S}; the character gives a direction (north, east, west, south) and $R$ is the number of unit steps the snake took in that direction.

For example, $T = 1$ with the pair 1 N means that when the seizure begins the snake is two squares long and its head is one square north of its tail; from there Alyona could move the snake north, east, or west on the next turn.

The input is guaranteed to satisfy:

• the total number of steps the snake takes in a single test case never exceeds 37, and
• the snake never intersects itself.

The input ends with a line containing a single 0, which must not be processed.

For each test case, print a single line containing the smallest number of moves Alyona must make so that the snake becomes doomed — that is, after her moves the snake has not yet crashed, but it is certain to crash into itself after some finite number of additional moves.