로봇 경로 디코딩

당신의 나라의 우주 기관이 방금 새로운 행성에 탐사 로버를 착륙시켰다. 행성의 표면은 $10^{9}$개의 열(서쪽에서 동쪽으로 1부터 번호가 매겨짐)과 $10^{9}$개의 행(북쪽에서 남쪽으로 1부터 번호가 매겨짐)으로 이루어진 정사각형 격자로 생각할 수 있다. w번째 열과 h번째 행에 있는 칸을 (w, h)로 나타낸다. 로버는 (1, 1) 칸에서 시작한다.

네 방위를 향한 이동을 나타내는 문자열이 포함된 프로그램을 전송하여 행성 표면에서 로버를 조종할 수 있다. 로봇은 문자열의 각 문자를 순서대로 실행한다. 로버는 다음 규칙에 따라 이동한다.

• N: 북쪽으로 한 단위 이동한다.

• S: 남쪽으로 한 단위 이동한다.

• E: 동쪽으로 한 단위 이동한다.

• W: 서쪽으로 한 단위 이동한다.

또한 특별한 명령어 X(Y)도 있다. 여기서 X은 2 이상 9 이하인 수이고, Y은 비어 있지 않은 하위 프로그램이다. 이는 로봇이 하위 프로그램 Y을 총 X번 반복해야 함을 뜻한다. 예를 들면 다음과 같다.

• 2(NWE)은 NWENWE과 동등하다.

• 3(S2(E))은 SEESEESEE과 동등하다.

• EEEE4(N)2(SS)은 EEEENNNNSSSS과 동등하다.

행성은 회전타원체이므로 첫 번째 열과 마지막 열은 인접해 있다. 따라서 $10^{9}$열에서 동쪽으로 이동하면 로버는 1열로 이동하고, $10^{9}$행에서 남쪽으로 이동하면 로버는 1행으로 이동한다. 마찬가지로 1열에서 서쪽으로 이동하면 로버는 $10^{9}$열로 이동하고, 1행에서 북쪽으로 이동하면 로버는 $10^{9}$행으로 이동한다. 로봇이 실행할 프로그램이 주어질 때, 모든 이동을 마친 후 로봇의 최종 위치를 구한다.

제한

시간 제한: 10초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 문자열은 유효한 프로그램을 나타낸다. 각 프로그램의 길이는 1자 이상 2000자 이하이다.

테스트 세트 1

로봇이 하나의 테스트 케이스에서 이동하는 총횟수는 최대 $10^{4}$이다.

테스트 세트 2

추가 제약 조건은 없다.

입력의 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄에는 로버에 전송된 프로그램인 하나의 문자열이 주어진다.

각 테스트 케이스마다 Case #x: w h을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호(1부터 시작)이고, w h은 로버가 최종적으로 도착하는 칸 (w, h)이다.

예제 케이스 #1에서 로버는 남쪽으로 세 단위 이동한 다음 동쪽으로 세 단위 이동한다.

예제 케이스 #2에서 로버는 북쪽으로 한 단위 이동한다. 행성이 원환면이므로 로버는 $10^{9}$행으로 이동한다.

예제 케이스 #3에서 로버에 주어진 프로그램은 NSSSNEEN과 동등하다.

예제 케이스 #4에서 로버에 주어진 프로그램은 NWNWNWWEEEEWWEEEEWNWNWNWWEEEEWWEEEEW과 동등하다.