F. Melody
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Little T came to City T, and she is going to a Livehouse for a performance.

City T can be represented by an infinite Euclidean 2D plane. The positive direction of the $$$y$$$-axis represents due north (N), the positive direction of the $$$x$$$-axis represents due east (E), the negative direction of the $$$y$$$-axis represents due south (S), and the negative direction of the $$$x$$$-axis represents due west (W).

Little T is initially standing at position $$$(x_{t}, y_{t})$$$, initially facing one of the four directions: due east, south, west, or north. The Livehouse she wants to go to is located at $$$(x_l, y_l)$$$.

For each move, she can choose one of the following two options:

  • Go straight, walk one unit length along the current direction.
  • Turn right, rotate the direction Little T is facing by $$$90^\circ$$$ clockwise (North turns to East, East turns to South, South turns to West, West turns to North).
  • Note that Little T cannot turn left or turn around.

Please calculate, under the above conditions, what is the minimum number of right turns Little T needs to make to reach the Livehouse.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^5$$$), representing the number of test cases.

For each test case, one line contains 5 elements $$$x_t$$$, $$$y_t$$$, $$$dir$$$, $$$x_l$$$, $$$y_l$$$ ($$$x_t, y_t, x_l, y_l \in \{n \in \mathbb{Z} : -10^9 \le n\le 10^9\}$$$, $$$dir \in \{\text{N}, \text{E}, \text{S}, \text{W}\}$$$), respectively representing Little T's location, the initial direction Little T is facing, and the location of the Livehouse.

Output

For each test case, output a single line with an integer representing the minimum number of right turns Little T needs to make to reach the Livehouse under the above conditions.

Example
Input
8
0 0 E 3 -2
1 1 N 0 1
10 10 E 10 10
-9 2 E 3 2
0 -7 E -1 -4
0 6 E -4 6
10 -9 S 10 9
1 -3 N -1 0
Output
1
3
0
0
3
2
2
3
Note

For the 1st test case, first walk $$$3$$$ steps east to reach $$$(3,0)$$$, then turn right to face south, and walk $$$2$$$ steps south to $$$(3, -2)$$$.

For the 2nd test case, first turn right three times to face west, then walk $$$1$$$ step to reach $$$(0, 1)$$$.

For the 3rd test case, the starting point and the ending point coincide, so no right turn is needed.