Stroll

A beautiful spring sun was shining outside the window, so Mr. Henryk decided to take a stroll around the city. He always walked straight ahead, changing direction only at the intersections he came across. Today was no exception. At some point he realized it had gotten quite late: to catch the next episode of his favorite TV series, he has to turn toward home right now.

The intersections in Mr. Henryk's city are laid out at regular intervals. From every intersection there are exactly four roads, one each leading north, south, east, and west. Walking along any single road in the city takes Mr. Henryk time $1$. How much time will he need to get home?

The first line contains the number of test sets $Z$ ($1 \le Z \le 10$), followed by the descriptions of the $Z$ tests. Each test consists of two lines. The first line contains a natural number $n$ ($1 \le n \le 500000$), the number of roads Mr. Henryk has already walked. The second line contains exactly $n$ uppercase letters N, S, W, E, denoting the directions Mr. Henryk chose at successive intersections (N - north, S - south, W - west, E - east).

For each test, output on its own line a single integer: the minimum amount of time Mr. Henryk needs to return home.