지나치게 흥분한 팬

오늘이 바로 그날이다. 마침내 고양이 Peppurr와 함께 사진을 찍게 되는 날이다!

Peppurr가 당신의 도시를 순회할 것이라는 발표가 방금 나왔다. 도시에는 남북 방향으로 뻗은 길이가 무한한 도로가 무한히 많고, 동서 방향으로 뻗은 길이가 무한한 도로도 무한히 많다. 교차로는 남북 방향 도로와 동서 방향 도로가 만나는 모든 지점이다. 임의의 교차로에서 북쪽, 동쪽, 남쪽, 서쪽 각 방향으로 가장 가까운 교차로는 정확히 한 블록 떨어져 있다.

당신은 Peppurr가 이 도로들을 따라 순회할 정확한 경로를 알고 있다. 목표는 Peppurr가 순회 중 방문하는 교차로 중 하나에 Peppurr와 동시에 도착하는 것이며, 가능한 한 빨리 그렇게 하고자 한다. 이것이 Peppurr와 함께 사진을 찍을 방법이다!

Peppurr의 순회는 당신이 현재 있는 교차로에서 동쪽으로 X블록, 북쪽으로 Y블록 떨어진 교차로에서 시작한다. 당신과 Peppurr는 모두 한 블록 전체를 걷는 데 정확히 일 분이 걸리고 매분이 끝날 때 교차로에 있어야 하며, 둘 중 누구도 블록의 일부만 걸을 수 없다.

Peppurr는 미리 정해진 경로를 따라 이동한다. 매분 동안 가만히 있거나, 4개 방향(북쪽, 동쪽, 남쪽, 서쪽) 중 하나로 한 블록 걸을 수 있다. 당신과 Peppurr는 모두 도로만 따라 걷는다.

당신과 Peppurr가 같은 시각에 같은 교차로에 있다면, 순회의 마지막 교차로에서도 사진을 찍을 수 있다. 하지만 순회가 끝난 뒤에는 Peppurr와 사진을 찍을 수 없으므로, 순회가 끝난 뒤 단 일 분이라도 늦게 순회의 마지막 교차로에 도착하면 사진을 찍지 못한다.

Peppurr와 함께 사진을 찍을 수 있는가? 가능하다면 얼마나 빨리 찍을 수 있는가?

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. (X, Y) ≠ (0, 0). (순회는 당신과 같은 교차로에서 시작하지 않는다.)

테스트 세트 1 (결과 공개)

0 ≤ X ≤ 10. 0 ≤ Y ≤ 10. 1 ≤ M의 길이 ≤ 8. M의 각 문자는 대문자이며, N 또는 S 중 하나이다.

테스트 세트 2 (결과 공개)

0 ≤ X ≤ 1000. 0 ≤ Y ≤ 1000. 1 ≤ M의 길이 ≤ 1000. M의 각 문자는 대문자이며, N 또는 S 중 하나이다.

테스트 세트 3 (결과 공개)

0 ≤ X ≤ 1000. 0 ≤ Y ≤ 1000. 1 ≤ M의 길이 ≤ 1000. M의 각 문자는 대문자이며, N, E, S, W 중 하나이다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 X와 Y, 그리고 문자열 M을 포함하는 한 줄로 이루어진다. 이는 Peppurr의 순회가 당신에게서 정확히 동쪽으로 X블록, 북쪽으로 Y블록 떨어진 곳에서 시작함을 나타낸다. 문자열 M은 Peppurr가 수행할 이동의 순서이다. M의 i번째 문자는 N, E, S, W 중 하나이며, 각각 Peppurr가 순회의 i번째 분 동안 한 블록 걸어갈 방향인 북쪽, 동쪽, 남쪽, 서쪽에 대응한다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며, 번호는 1부터 시작한다. Peppurr와 함께 사진을 찍을 방법이 없다면 y는 IMPOSSIBLE이다. 그렇지 않다면 y는 순회가 시작된 시점부터 Peppurr와 함께 사진을 찍기까지 필요한 최소 시간(분)이다.

예제 케이스 #1에서는 동쪽으로 네 블록 걸어가면 순회의 마지막 교차로에서 Peppurr와 함께 사진을 찍을 수 있다.

예제 케이스 #2에서는 순회가 당신에게서 정확히 동쪽으로 세 블록 떨어진 곳에서 시작한다. 어떻게 이동하더라도 Peppurr와 함께 사진을 찍을 수 없다.

예제 케이스 #3에서는 순회 경로가 너무 북쪽에 있어서 순회가 끝나기 전에 사진을 찍을 수 없다.

예제 케이스 #4에서는 순회가 일 분 뒤에 당신이 있는 곳으로 오므로, 움직일 필요조차 없다! Peppurr와 함께 즐겁게 사진을 찍자! 사진은 교차로에서만 찍을 수 있다는 점을 기억해야 한다. 따라서 순회가 남쪽으로 이동하는 동안 당신이 북쪽으로 이동하여 교차로가 아닌 곳에서 Peppurr와 서로 지나치게 된다면, 0.5분 만에 사진을 찍을 수 없다.

예제 케이스 #5에서는 북쪽으로 두 번 이동한 다음 동쪽으로 두 번 이동할 수 있다. 그 뒤 가만히 있으면 다음 분에 Peppurr와 함께 사진을 찍을 수 있다. 5분 만에 Peppurr와 함께 사진을 찍을 수 있는 다른 경로들도 있지만, 그보다 빨리 찍을 수 있는 경로는 없다.

다음 두 케이스는 테스트 세트 1이나 테스트 세트 2에는 나올 수 없지만, 테스트 세트 3에는 나올 수 있다.

이 두 케이스의 올바른 출력은 다음과 같다.

케이스 #1에서는 원래 출발점에서 남쪽으로 한 블록, 동쪽으로 두 블록 떨어진 곳에서 Peppurr와 함께 사진을 찍을 수 있음에 유의한다.

케이스 #2에서 Peppurr는 작은 정사각형을 따라 이동한다. Peppurr가 그 정사각형의 출발점으로 돌아올 때 사진을 찍을 수 있다.