산책

창밖으로 아름다운 봄 햇살이 비치자, 헨리크 씨는 도시를 한 바퀴 산책하기로 마음먹었습니다. 그는 언제나 곧장 앞으로만 걸었고, 방향을 바꾸는 것은 오직 마주치는 교차로에서뿐이었습니다. 오늘도 마찬가지였습니다. 그러다 문득 시간이 꽤 늦었다는 것을 깨달았습니다. 좋아하는 드라마의 다음 회를 놓치지 않으려면, 지금 당장 집 쪽으로 방향을 돌려야 합니다.

헨리크 씨가 사는 도시의 교차로는 일정한 간격으로 놓여 있습니다. 각 교차로에서는 정확히 네 갈래의 길, 즉 북쪽, 남쪽, 동쪽, 서쪽으로 하나씩 뻗어 있습니다. 도시의 길 하나를 지나는 데는 시간 $1$ 이 걸립니다. 집에 도착하려면 최소 얼마의 시간이 필요할까요?

첫째 줄에 테스트 세트의 개수 $Z$ ($1 \le Z \le 10$) 가 주어지고, 이어서 $Z$ 개의 테스트가 주어집니다. 각 테스트는 두 줄로 이루어집니다. 첫째 줄에는 헨리크 씨가 이미 걸어간 길의 개수를 나타내는 자연수 $n$ ($1 \le n \le 500000$) 이 주어집니다. 둘째 줄에는 헨리크 씨가 각 교차로에서 선택한 방향을 나타내는 대문자 N, S, W, E 가 정확히 $n$ 개 주어집니다 (N - 북쪽, S - 남쪽, W - 서쪽, E - 동쪽).

각 테스트마다, 헨리크 씨가 집으로 돌아가는 데 필요한 최소 시간을 나타내는 정수 하나를 한 줄에 출력합니다.