MOULDS - Moulds

no tags 

In a factory, moulds for casting metal objects are produced by a special cutting device. The device is equipped with cuboid-shaped blade of size 1 mm x 1 mm x 30 mm (its height) which operates with each of its sides thus producing the mould from cuboid of size 250 mm x 250 mm x 30 mm (its height). The end of the blade newer lowers below the bottom surface of the cuboid. In any moment the distance between initial and current position doesn't exceed 1000.

The machine understands special command language which has the following grammar:

<command block> ::= [ <command> ; {<command> ; } ]
<command>       ::= <lift> | <shift> | <command block>
<lift>          ::= ^ <distance>
<shift>         ::= @ <direction> <distance>
<direction>     ::= N | S | W | E
<distance>      ::= <sign> <number> | <number>
<number>        ::= <digit> {<digit>}
<sign>          ::= - | +
<digit>         ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

where {exp} means zero or more exps. 

The command <lift> causes moving the blade downwards when the distance is a positive number and upwards otherwise. The command <shift> moves the blade in the appropriate direction (N--north, S--south, W--west, E--east).

Task

Write a program which for each data set from a sequence of several data sets:

  • reads a command block from input,
  • computes the volume of hollows made by the machine commanded by a given command block (assuming that before the execution the blade is located 1 mm above the north-west corner of the virgin cuboid),
  • writes the result to output.

Input

The first line of the input file contains one integer d, 1 <= d <= 10, which is the number of data sets. The data sets follow. Each data set occupies one line of the input file and is a word derived from <command block> of the above grammar of length not exceeding 10000 characters.

Output

The i-th line of the output file should contain one integer -- the volume (in cubic mm) of the hollows made by the machine controlled by the command block given in the i-th data set.

Example

Sample input:
1
[^2;@S2;]

Sample output:
3

hide comments

Added by:adrian
Date:2004-06-08
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:III Polish Collegiate Team Programming Contest (AMPPZ), 1998