I. NEWS
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Xiao Ming is obsessed with a strange game that takes place on a 2D coordinate plane. He controls a small airplane starting at the origin point $$$(0,0)$$$.

As a top pilot, he receives a flight command sequence, which is a permutation $$$P$$$ of the four letters 'NEWS'.

Xiao Ming will perform $$$n$$$ flights in total. For his $$$i$$$-th flight:

If $$$1 \le i \le 4$$$, the flight command is the $$$i$$$-th letter in $$$P$$$.

If $$$i \gt 4$$$, the flight command is the same as the $$$(i-4)$$$-th flight.

The meaning of each command is as follows:

'N': If the current position is $$$(x,y)$$$, move to $$$(x,y+1)$$$. Repeat this until reaching a new unvisited point.

'E': If the current position is $$$(x,y)$$$, move to $$$(x+1,y)$$$. Repeat this until reaching a new unvisited point.

'W': If the current position is $$$(x,y)$$$, move to $$$(x-1,y)$$$. Repeat this until reaching a new unvisited point.

'S': If the current position is $$$(x,y)$$$, move to $$$(x,y-1)$$$. Repeat this until reaching a new unvisited point.

After completing all $$$n$$$ flights, calculate the sum of the two coordinates of his final position.

Input

The first line contains a positive integer $$$T$$$ — the number of test cases.

Each of the next $$$T$$$ lines contains a test case: a positive integer $$$n$$$ and a 4-letter string $$$P$$$, separated by a space.

$$$1 \le T \le 10^5$$$, $$$1 \le n \le 10^9$$$, $$$P$$$ has exactly 4 letters, with each of 'N', 'E', 'W', 'S' appearing exactly once.

Output

For each test case, output one line with the sum of the two coordinates of the final position.

Example
Input
6
9 NEWS
9 NESW
9 NSEW
1000000000 SEWN
1000000000 SWNE
1000000000 SNWE
Output
1
-1
-3
-499999999
250000000
500000000
Note

When $$$n=9$$$ and $$$P=$$$ 'NEWS', the positions after each flight are (starting from $$$(0,0)$$$): $$$(0,0)$$$, $$$(0,1)$$$, $$$(1,1)$$$, $$$(-1,1)$$$, $$$(-1,0)$$$, $$$(-1,2)$$$, $$$(0,2)$$$, $$$(-2,2)$$$, $$$(-2,1)$$$, $$$(-2,3)$$$.

For the 'W' command at $$$(1,1)$$$, the plane first tries to move to $$$(0,1)$$$. But $$$(0,1)$$$ is visited, so he continues moving to $$$(-1,1)$$$.