꿈틀거리는 뱀

자하르(Zakhar)는 무한이라는 개념에 익숙해지기 위해, 무한히 긴 뱀을 가지고 무한 격자 위에서 스네이크 게임을 변형한 버전을 즐기고 있습니다. 뱀은 격자 위 임의의 위치에서 한 칸짜리로 시작합니다. 매 이동마다 뱀은 한 칸씩 자랍니다. 플레이어는 현재 머리 칸과 상하좌우로 인접한 빈 칸 하나를 고르고, 그 칸이 새로운 머리 칸이 됩니다. 꼬리는 절대 움직이지 않습니다. 즉 뱀이 어떤 칸을 한 번 차지하면, 뱀의 일부가 그 칸에 영원히 남습니다. 자하르는 이 게임의 끝없는 플레이를 즐깁니다.

자하르는 가끔 몇 순간 동안만 지속되는 짧은 결신 발작을 겪는데, 본인은 전혀 알아채지 못합니다. 여동생 알료나(Alyona)는 이런 의식의 빈틈을 노려 오빠에게 장난을 치고 싶어 합니다. 그녀는 뱀을 파멸이 확정된 상태로 몰아넣으려 합니다. 즉, 아직 뱀이 자신과 충돌하지는 않았지만, 이후 어떻게 움직이더라도 유한한 횟수의 이동 뒤에는 반드시 자기 몸과 충돌하게 되는 상태입니다. 자하르가 언제든 발작에서 깨어날 수 있으므로, 알료나는 최대한 빨리 움직여야 합니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 정수 $T$ 하나가 적힌 줄로 시작하며, $T$는 자하르가 결신 발작을 일으키기 전까지 뱀이 이동한 횟수입니다. 다음 줄에는 $T$개의 쌍이 주어집니다. 각 쌍은 양의 정수 $R$과 집합 {N, E, W, S}의 문자 하나로 이루어지며, 문자는 방향(북, 동, 서, 남)을 나타내고 $R$은 그 방향으로 뱀이 이동한 칸 수입니다.

예를 들어 $T = 1$이고 쌍이 1 N이면, 발작이 시작될 때 뱀은 길이가 두 칸이고 머리가 꼬리의 바로 북쪽에 있다는 뜻입니다. 이 상태에서 알료나는 다음 차례에 뱀을 북, 동, 또는 서쪽으로 움직일 수 있습니다.

입력은 다음을 만족함이 보장됩니다.

• 한 테스트 케이스에서 뱀이 이동하는 전체 칸 수는 37을 넘지 않으며,
• 뱀은 절대 자기 자신과 교차하지 않습니다.

입력의 끝은 0 하나만 적힌 줄로 표시되며, 이 줄은 처리하지 않습니다.

각 테스트 케이스마다, 뱀을 파멸이 확정된 상태로 만들기 위해 알료나가 해야 하는 최소 이동 횟수를 한 줄에 하나씩 출력하세요. 즉, 그녀의 이동이 끝난 뒤 뱀은 아직 충돌하지 않았지만, 유한한 횟수의 추가 이동 뒤에는 반드시 자기 몸과 충돌하게 되는 상태로 만드는 데 필요한 최소 이동 횟수입니다.