Smooth operator

Since the early childhood John was very curious about all vehicles. In addition he was also interested in brain teasers. His house is surrounded by a vast beautiful garden which, unfortunately requires frequent care. Both John's hobbies were combined on the day when his parents bought him four-wheel lawn mower. Since that day John mows the grass twice a week and every time he tries to optimize his route over the garden to finish his task in the quickest way.


Each garden is divided into squares of unit size (i.e. 1x1). John is able to move from square to square in any of four possible directions (say North, East, South or West). We assume that every square of the garden is covered by grass (thus there is no holes that needed to be omitted). John's task is to mow all the grass in the garden so he needs to visit every square. He starts from a given square which is also the end point for his route. The length of the route should be as short as possible.

The first line of the input contains the number of gardens t ≤ 10 (i.e. the number of test cases). Each test case defines the shape of the garden in the form of the definition of surrendering fence. The first line of each test case contains the number of segments which form the fence (4 ≤ n ≤ 20000). The second line contains exactly n integer numbers a1,...,an which are the lengths of subsequent segments of the fence (1 ≤ |ai| ≤ 250). We assume that every two consecutive segments are perpendicular. The length of ith segment is equal to the module of its value and the sign defines direction (+ is for North or East and - is for South and West). The first segment is always directed vertically (i.e. in North or South direction) and the fence is defined according to a clockwise direction. The John's staring position is defined by the beginning of the first segment. The whole garden can be embedded into the big square of the size 1010x1010.

For better understanding the specification of the input consider the following example:

// the part of the input
+2 +1 +2 +2 -1 +2 -3 -1 +1 -1 +1 -1 -2 -2

Example Input


For each test case print the number of moves and after the space the sequence of the moves of John's mower using the directions: N for North, E for East, S for South and W for West. Separate answers for distinct test cases with the new line.

The possible answer for previously given example:

// the part of the output

Example Output


Your program will be independently executed three times, each time with different input data and the overall result will be equal to:

sum(max{(3 - scorei) * 3; 0},i=1,2,3)

Where the scorei is the score for the ith execution. For each execution the score is the sum (over all test cases) of the proportions of the length of John's route to the size of the garden (i.e. the number of its unit squares).


+1 +1 +1 +1 -1 +1 -1 -1 -1 -1 +1 -1
+2 +1 -2 -1
+2 +1 +2 +2 -1 +2 -3 -1 +1 -1 +1 -1 -2 -2
-2 -1 +1 -3 +2 +3 -1 +1
+7 +1 -3 +1 +3 +1 -7 -1 +1 -1 -1 -1

2 NS

Please log in to submit your solution.