Plane

A woman is walking on an infinite plane (a mathematical plane, not an airplane) divided into squares. She can move one square to the north, south, east, or west with each step. You will be given the walk this woman takes on this plane. You are to print out the number of distinct squares (including her starting square) that she visited on the walk. A square only counts once in the count, no matter how many times it has been visited (provided that it HAS been visited).

Input Specification

The first line of the input will consist of a decimal integer N between 1 and 100 inclusive, representing the number of test cases that will follow. What will then follow are N lines, corresponding to the test cases. Each line will contain a string of characters from {N, S, E, W} of length between 0 and 80 inclusive. This string corresponds to the steps the woman takes as she walks along the plane. There will be no spaces anywhere in the input and no extra newline characters.

Output Specification

The test cases in the output should appear in the order in which they appear in the input. Each test case in the output will be a positive decimal integer, followed by a newline character, equal to the number of squares the woman has visited. No extra newline characters should appear in the output.

Sample Input

1. 2
2. SSSSSSSSSS
3. NSEWNSEWNSEWNSEWNSEWNSEW

download as text file

Output for Sample Input

1. 11
2. 3

download as text file

Original Problem

NMU Invitational Programming Contest, 2000