Erratic Ants

An ant colony is out looking for food. The ground around the colony is full of traps and obstacles, and predators are hiding there too, so foraging is hard. Luckily the colony has one ant who fits the job. Max is neither clever nor diligent, but his luck holds. On every trip he has ever made he stayed on safe ground, and sooner or later he always reached a food source and reported it back.

The trouble is that Max almost never walks anything close to a shortest route. He does report the path he took, one step at a time and exactly, however long and winding it is. Find the shortest route contained in the directions Max reported, so the colony can carry food with less walking.

The first line contains the number of paths Max reported, $n$ ($1 \le n \le 100$). A blank line follows, then the descriptions of the $n$ paths. A blank line separates each pair of path descriptions.

Each path description starts with the number of steps in that path, $s$ ($0 \le s \le 60$). The next $s$ lines each contain one of the upper-case letters N, E, S, W, meaning a step to the north, east, south, or west. Each step moves Max one unit of distance. Every path starts at the colony and ends at a food source.

When you look for a shortest route, you may only take steps that Max already took, or those same steps in reverse.

For each path, print the number of steps in a shortest route from the colony to that path's food source, one integer per line, in the order the paths are given.