P16398 [ECUSTPC 2026 Spring] Lost Day.

:::epigraph 月が話しかけてきた そして不思議な力をくれた Maybe we should swap the title. :::

T came to City T, and she wants to go to a Livehouse show. City T can be represented as an infinite Euclidean 2D plane. The positive direction of the $y$-axis is due north (N), the positive direction of the $x$-axis is due east (E), the negative direction of the $y$-axis is due south (S), and the negative direction of the $x$-axis is due west (W). T initially stands at $(x_t, y_t)$, initially facing one of the four directions: east, south, west, or north. The Livehouse she wants to go to is at $(x_l, y_l)$. Each move, she may choose one of the following two actions: - Go straight: move 1 unit length along the current direction. - Turn right: rotate T's facing direction clockwise by $90^\circ$ (north to east, east to south, south to west, west to north). Note that T cannot turn left or make a U-turn. Find the minimum number of **right turns** T needs to reach the Livehouse under the above conditions. It can be proven that under these rules, the target position is always reachable.

The first line contains an integer $T \ (1 \le T \le 10^5)$, the number of testdata. Each testdata consists of one line with 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 \{\texttt{N}, \texttt{E}, \texttt{S}, \texttt{W}\})$, representing T's position, T's initial facing direction, and the Livehouse position.

For each testdata, output one line containing one integer, the minimum number of **right turns** needed for T to reach the Livehouse under the above conditions.

### Sample 1 Explanation For the 1st testdata, first walk 3 steps to the east to reach $(3, 0)$, then turn right to face south, and walk 2 steps south to reach $(3, -2)$. For the 2nd testdata, first turn right three times to face west, then walk 1 step to reach $(0, 1)$. For the 3rd testdata, the start and end positions coincide, so no right turns are needed. Translated by ChatGPT 5