갈팡질팡 개미

개미 군락이 먹이를 찾아 나선다. 군락 주변에는 함정과 장애물이 널려 있고 천적도 숨어 있어서 먹이를 구하기가 쉽지 않다. 다행히 이 일에 딱 맞는 개미가 한 마리 있다. 맥스는 영리하지도 않고 부지런하지도 않지만 운이 아주 좋다. 지금까지 돌아다닌 모든 여정에서 맥스는 늘 안전한 땅만 밟았고, 언젠가는 반드시 먹이가 있는 곳에 닿아 군락에 알렸다.

문제는 맥스가 최단 경로 비슷한 길조차 거의 밟지 않는다는 점이다. 대신 맥스는 자기가 지나온 길을, 아무리 구불구불하고 복잡해도, 한 걸음씩 정확히 전해 준다. 맥스가 알려 준 이 복잡한 경로 안에 들어 있는 최단 경로를 찾아서 군락이 먹이를 더 효율적으로 나르도록 도와라.

첫째 줄에 맥스가 보고한 경로의 개수 $n$ ($1 \le n \le 100$)이 주어진다. 그다음 빈 줄이 하나 오고, 이어서 경로 $n$개의 설명이 주어진다. 경로 설명 사이에는 빈 줄이 하나씩 들어간다.

각 경로 설명은 그 경로의 걸음 수 $s$ ($0 \le s \le 60$)로 시작한다. 이어지는 $s$개의 줄에는 각각 대문자 N, E, S, W 중 하나가 들어 있고, 차례대로 북쪽, 동쪽, 남쪽, 서쪽으로 한 걸음 옮긴다는 뜻이다. 한 걸음은 거리 1만큼 이동한다. 모든 경로는 군락에서 시작해 먹이가 있는 곳에서 끝난다.

최단 경로를 찾을 때는 맥스가 이미 밟은 걸음이나 그 걸음을 거꾸로 되짚는 걸음만 밟을 수 있다.

경로마다 군락에서 그 경로의 먹이까지 가는 최단 경로의 걸음 수를 한 줄에 하나씩, 입력에 주어진 순서대로 출력한다.